Вам дана доска с целочисленной матрицей n x n, клетки которой помечены метками от 1 до n2 в стиле Бустрофедона, начиная с левого нижнего края доски (т.е. board[n - 1][0]) и чередуя направление в каждой строке. Вы начинаете на клетке 1 доски. В каждый ход, начиная с клетки curr, вы делаете следующее: выбираете клетку назначения next с меткой в диапазоне [curr + 1, min(curr + 6, n2)]. Этот выбор имитирует результат стандартного броска 6-гранного кубика: то есть всегда существует не более 6 мест назначения, независимо от размера доски. Если next имеет змейку или лестницу, вы должны двигаться к месту назначения этой змейки или лестницы. В противном случае вы переходите на следующий. Игра заканчивается, когда вы достигаете клетки n2. Клетка доски в строке r и столбце c имеет змейку или лестницу, если board[r][c] != -1. Местом назначения этой змейки или лестницы является доска[r][c]. В клетках 1 и n2 нет змейки или лестницы. Обратите внимание, что вы можете взять змейку или лестницу не более одного раза за ход. Если конечный пункт змейки или лестницы является началом другой змейки или лестницы, вы не ходите по последующей змейке или лестнице. НаExemple, предположим, что доска имеет вид [[-1,4],[-1,3]], и на первом ходу ваш конечный квадрат - 2. Вы ходите по лестнице до квадрата 3, но не ходите по последующей лестнице до 4. return наименьшее количество ходов, необходимое для достижения квадрата n2. Если достичь квадрата невозможно, return -1.
Exemple:
Input: board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]]
Output: 4
C# solution
correspondant/originalusing System;
using System.Collections.Generic;
public class Solution {
public int SnakesAndLadders(int[][] board) {
int n = board.Length;
int[] GetPos(int x) {
int quot = (x - 1) / n;
int rem = (x - 1) % n;
int row = n - 1 - quot;
int col = (row % 2 != n % 2) ? rem : n - 1 - rem;
return new int[] { row, col };
}
var visited = new HashSet<int>();
var queue = new Queue<int[]>();
queue.Enqueue(new int[] { 1, 0 });
while (queue.Count > 0) {
var curr = queue.Dequeue();
int pos = curr[0];
int steps = curr[1];
for (int i = 1; i <= 6; i++) {
int nextPos = pos + i;
if (nextPos > n * n) continue;
var rc = GetPos(nextPos);
int r = rc[0], c = rc[1];
if (board[r][c] != -1) {
nextPos = board[r][c];
}
if (nextPos == n * n) {
return steps + 1;
}
if (!visited.Contains(nextPos)) {
visited.Add(nextPos);
queue.Enqueue(new int[] { nextPos, steps + 1 });
}
}
}
return -1;
}
}C++ solution
brouillon automatique, à relire avant soumission#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public int SnakesAndLadders(int[][] board) {
int n = board.size();
vector<int>& GetPos(int x) {
int quot = (x - 1) / n;
int rem = (x - 1) % n;
int row = n - 1 - quot;
int col = (row % 2 != n % 2) ? rem : n - 1 - rem;
return new int[] { row, col };
}
var visited = new HashSet<int>();
var queue = new queue<int[]>();
queue.Enqueue(new int[] { 1, 0 });
while (queue.size() > 0) {
var curr = queue.Dequeue();
int pos = curr[0];
int steps = curr[1];
for (int i = 1; i <= 6; i++) {
int nextPos = pos + i;
if (nextPos > n * n) continue;
var rc = GetPos(nextPos);
int r = rc[0], c = rc[1];
if (board[r][c] != -1) {
nextPos = board[r][c];
}
if (nextPos == n * n) {
return steps + 1;
}
if (!visited.Contains(nextPos)) {
visited.push_back(nextPos);
queue.Enqueue(new int[] { nextPos, steps + 1 });
}
}
}
return -1;
}
}Java solution
correspondant/originalimport java.util.*;
class Solution {
public int snakesAndLadders(int[][] board) {
int n = board.length;
int[] getPos(int x) {
int quot = (x - 1) / n;
int rem = (x - 1) % n;
int row = n - 1 - quot;
int col = (row % 2 != n % 2) ? rem : n - 1 - rem;
return new int[]{row, col};
}
Set<Integer> visited = new HashSet<>();
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{1, 0});
while (!queue.isEmpty()) {
int[] curr = queue.poll();
int pos = curr[0];
int steps = curr[1];
for (int i = 1; i <= 6; i++) {
int nextPos = pos + i;
if (nextPos > n * n) continue;
int[] rc = getPos(nextPos);
int r = rc[0], c = rc[1];
if (board[r][c] != -1) {
nextPos = board[r][c];
}
if (nextPos == n * n) {
return steps + 1;
}
if (!visited.contains(nextPos)) {
visited.add(nextPos);
queue.offer(new int[]{nextPos, steps + 1});
}
}
}
return -1;
}
}Go solution
correspondant/originalusing System;
using System.Collections.Generic;
public class Solution {
public int SnakesAndLadders(int[][] board) {
int n = board.Length;
int[] GetPos(int x) {
int quot = (x - 1) / n;
int rem = (x - 1) % n;
int row = n - 1 - quot;
int col = (row % 2 != n % 2) ? rem : n - 1 - rem;
return new int[] { row, col };
}
var visited = new HashSet<int>();
var queue = new Queue<int[]>();
queue.Enqueue(new int[] { 1, 0 });
while (queue.Count > 0) {
var curr = queue.Dequeue();
int pos = curr[0];
int steps = curr[1];
for (int i = 1; i <= 6; i++) {
int nextPos = pos + i;
if (nextPos > n * n) continue;
var rc = GetPos(nextPos);
int r = rc[0], c = rc[1];
if (board[r][c] != -1) {
nextPos = board[r][c];
}
if (nextPos == n * n) {
return steps + 1;
}
if (!visited.Contains(nextPos)) {
visited.Add(nextPos);
queue.Enqueue(new int[] { nextPos, steps + 1 });
}
}
}
return -1;
}
}Algorithm
Представить доску в виде одномерного tableauа, чтобы легко определить позицию следующего хода.
Использовать BFS (Breadth-first search) для минимизации количества ходов до клетки n2.
В каждом ходе проверять клетки от curr + 1 до min(curr + 6, n2) и перемещаться по змейкам и лестницам, если они существуют.
Если достижение клетки n2 невозможно, вернуть -1.
😎
Vacancies for this task
offres actives with overlapping task tags are affichés.