?
2596.?檢查騎士巡視方案
騎士在一張?
n x n?的棋盤(pán)上巡視。在?有效?的巡視方案中，騎士會(huì)從棋盤(pán)的?左上角?出發(fā)，并且訪(fǎng)問(wèn)棋盤(pán)上的每個(gè)格子?恰好一次?。給你一個(gè)?
n x n?的整數(shù)矩陣?grid?，由范圍?[0, n * n - 1]?內(nèi)的不同整數(shù)組成，其中?grid[row][col]?表示單元格?(row, col)?是騎士訪(fǎng)問(wèn)的第?grid[row][col]?個(gè)單元格。騎士的行動(dòng)是從下標(biāo)?0?開(kāi)始的。如果?
grid?表示了騎士的有效巡視方案，返回?true；否則返回?false。注意，騎士行動(dòng)時(shí)可以垂直移動(dòng)兩個(gè)格子且水平移動(dòng)一個(gè)格子，或水平移動(dòng)兩個(gè)格子且垂直移動(dòng)一個(gè)格子。下圖展示了騎士從某個(gè)格子出發(fā)可能的八種行動(dòng)路線(xiàn)。
示例 1：
輸入：grid = [[0,11,16,5,20],[17,4,19,10,15],[12,1,8,21,6],[3,18,23,14,9],[24,13,2,7,22]] 輸出：true 解釋?zhuān)?/strong>grid 如上圖所示，可以證明這是一個(gè)有效的巡視方案。示例 2：
輸入：grid = [[0,3,6],[5,8,1],[2,7,4]] 輸出：false 解釋?zhuān)?/strong>grid 如上圖所示，考慮到騎士第 7 次行動(dòng)后的位置，第 8 次行動(dòng)是無(wú)效的。提示：
n == grid.length == grid[i].length3 <= n <= 70 <= grid[row][col] < n * ngrid?中的所有整數(shù)?互不相同
思路：?
初始為x，y?每一次移動(dòng)后是一個(gè)x1 y1? ?|(x1-x)*(y1-y)| 一定為2，所以就出來(lái)了
用表示1的位置與0的位置此方法進(jìn)行計(jì)算 然后2對(duì)應(yīng)的x2 y2索引與1.......全部滿(mǎn)足就返回true文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-709644.html
但是0 到1到2...的數(shù)字位置不知道，所以這時(shí)候用一個(gè)容器進(jìn)行排序。具體看題解?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-709644.html
class Solution {
public:
bool checkValidGrid(vector<vector<int>>& grid) {
if(grid[0][0]!=0) //如果騎士不在(0,0)的位置返回false
{
return false;
}
int n=grid.size();
vector<array<int,2>> arr(n*n);//定義一個(gè)n*n的容器 其中每個(gè)元素都是長(zhǎng)度為2的數(shù)組
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
arr[grid[i][j]]={i,j}; //將0到n*n的對(duì)應(yīng)的索引放在容器中。
}
}
for(int i=1;i<n*n;i++)
{
if(abs(arr[i][0]-arr[i-1][0])*abs(arr[i][1]-arr[i-1][1])!=2) //因?yàn)殚_(kāi)始的位置與移動(dòng)
//后的位置一定是 一個(gè)1*2的長(zhǎng)方形對(duì)角
//絕對(duì)值的差值為2
return false;
}
return true;
}
};到了這里，關(guān)于leecode 每日一題 2596. 檢查騎士巡視方案的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
