Вам дана доска с целочисленной матрицей 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 нет змейки или лестницы. Обратите внимание, что вы можете взять змейку или лестницу не более одного раза за ход. Если конечный пункт змейки или лестницы является началом другой змейки или лестницы, вы не ходите по последующей змейке или лестнице. На例, предположим, что доска имеет вид [[-1,4],[-1,3]], и на первом ходу ваш конечный квадрат - 2. Вы ходите по лестнице до квадрата 3, но не ходите по последующей лестнице до 4. return наименьшее количество ходов, необходимое для достижения квадрата n2. Если достичь квадрата невозможно, return -1.
例:
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# 解法
照合済み/オリジナルusing 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++ 解法
自動ドラフト、提出前に確認#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 解法
照合済み/オリジナルimport 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 解法
照合済み/オリジナルusing 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
Представить доску в виде одномерного 配列а, чтобы легко определить позицию следующего хода.
Использовать BFS (Breadth-first search) для минимизации количества ходов до клетки n2.
В каждом ходе проверять клетки от curr + 1 до min(curr + 6, n2) и перемещаться по змейкам и лестницам, если они существуют.
Если достижение клетки n2 невозможно, вернуть -1.
😎
Vacancies for this task
有効な求人 with overlapping task tags are 表示.