問(wèn)題描述
N x N 的棋盤 board 上祷肯，按從 1 到 N * N 的數(shù)字給方格編號(hào)，編號(hào) 從左下角開(kāi)始疗隶，每一行交替方向佑笋。
例如，一塊 6 x 6 大小的棋盤斑鼻，編號(hào)如下：
r行 c 列的棋盤蒋纬，按前述方法編號(hào)，棋盤格中可能存在 “蛇” 或 “梯子”坚弱；如果 board[r][c] != -1蜀备，那個(gè)蛇或梯子的目的地將會(huì)是 board[r][c]。
玩家從棋盤上的方格 1 （總是在最后一行史汗、第一列）開(kāi)始出發(fā)琼掠。
每一回合，玩家需要從當(dāng)前方格 x 開(kāi)始出發(fā)停撞，按下述要求前進(jìn)：
選定目標(biāo)方格：選擇從編號(hào) x+1瓷蛙，x+2，x+3戈毒，x+4艰猬，x+5，或者 x+6 的方格中選出一個(gè)目標(biāo)方格 s 埋市，目標(biāo)方格的編號(hào) <= N * N冠桃。
該選擇模擬了擲骰子的情景，無(wú)論棋盤大小如何道宅，你的目的地范圍也只能處于區(qū)間 [x+1, x+6] 之間食听。
傳送玩家：如果目標(biāo)方格 S 處存在蛇或梯子胸蛛，那么玩家會(huì)傳送到蛇或梯子的目的地。否則樱报，玩家傳送到目標(biāo)方格 S葬项。
注意，玩家在每回合的前進(jìn)過(guò)程中最多只能爬過(guò)蛇或梯子一次：就算目的地是另一條蛇或梯子的起點(diǎn)迹蛤，你也不會(huì)繼續(xù)移動(dòng)民珍。
返回達(dá)到方格 N*N 所需的最少移動(dòng)次數(shù)，如果不可能盗飒，則返回 -1嚷量。
Example
示例圖見(jiàn) “問(wèn)題描述” 中的圖片
輸入：[
[-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]]
輸出：4
解釋：
首先，從方格 1 [第 5 行逆趣，第 0 列] 開(kāi)始蝶溶。
你決定移動(dòng)到方格 2，并必須爬過(guò)梯子移動(dòng)到到方格 15宣渗。
然后你決定移動(dòng)到方格 17 [第 3 行身坐，第 5 列]，必須爬過(guò)蛇到方格 13落包。
然后你決定移動(dòng)到方格 14部蛇，且必須通過(guò)梯子移動(dòng)到方格 35。
然后你決定移動(dòng)到方格 36, 游戲結(jié)束咐蝇。
可以證明你需要至少 4 次移動(dòng)才能到達(dá)第 N*N 個(gè)方格涯鲁，所以答案是 4。
Note
- 2 <= board.length = board[0].length <= 20
- board[i][j] 介于 1 和 N*N 之間或者等于 -1有序。
- 編號(hào)為 1 的方格上沒(méi)有蛇或梯子抹腿。
- 編號(hào)為 N*N 的方格上沒(méi)有蛇或梯子。
題目鏈接：909. 蛇梯棋 (難度:中等)
思路
這個(gè)問(wèn)題有兩個(gè)關(guān)鍵點(diǎn)旭寿，一個(gè)是要將給定的編號(hào) num 轉(zhuǎn)換為棋盤上對(duì)應(yīng)的坐標(biāo)(x , y)警绩；另一個(gè)則是要注意，由于梯子和蛇都是必須要經(jīng)過(guò)的盅称，因此棋盤當(dāng)中可能會(huì)存在環(huán)肩祥。
對(duì)于第一個(gè)任務(wù)，我們只需要去模擬棋盤上數(shù)字的分布規(guī)律即可缩膝。
對(duì)于第二個(gè)任務(wù)混狠，我們可以用一個(gè) visited 數(shù)組來(lái)標(biāo)記所有經(jīng)過(guò)的點(diǎn)(包含了用骰子擲出來(lái)的編號(hào)，也包含了利用蛇或是梯子經(jīng)過(guò)的點(diǎn)的編號(hào))疾层。雖然棋盤規(guī)則當(dāng)中沒(méi)有規(guī)定走過(guò)的點(diǎn)不能重復(fù)走将饺，但是由于題目要求的是移動(dòng)的最小次數(shù)，而重復(fù)走的點(diǎn)對(duì)于最小移動(dòng)次數(shù)是沒(méi)有貢獻(xiàn)的，因此該策略是完備的(即只要有解就必定能搜出來(lái)予弧，如果搜不出來(lái)說(shuō)明必定沒(méi)有解)刮吧。
代碼
class Solution {
public:
inline void getCoordinate(int N,int num, int& row, int& col){
row = N - 1 - (num - 1) / N;
int tmp = (num - 1) % N;
col = (N - row) & 1 ? tmp : N - 1 - tmp;
}
int snakesAndLadders(vector<vector<int>>& board) {
int N = board.size();
vector<vector<bool>> visited(N, vector<bool>(N, false));
queue<int> my_queue;
my_queue.push(1);
int times = 0;
bool flag = false;
while(!my_queue.empty()){
int len = my_queue.size();
for(int i = 0;i < len;++i){
auto cur = my_queue.front();
my_queue.pop();
if(cur == N * N){
flag = true;
break;
}
for(int j = 1;j <= 6;++j){
int num = cur + j;
if(num > N * N)
break;
int nx = 0, ny = 0;
getCoordinate(N,num, nx, ny);
if(visited[nx][ny])
continue;
visited[nx][ny] = true;
if(board[nx][ny] == -1){
my_queue.push(num);
}else{
my_queue.push(board[nx][ny]);
visited[nx][ny] = true;
}
}
}
if(flag)
break;
++times;
}
return flag ? times : -1;
}
};
執(zhí)行結(jié)果： 32 ms, 12 MB
