题解:根据描述,第一反应,由数据范围,满足题意的3×3的矩阵,从3×3矩阵的中间元素暴力枚举。
如何判断一个3×3矩阵是幻方的?首先这9个数均不相同,其次这9个数范围为1-9。最后每一行每一列,和对角线元素和均为15,最中间元素为5。
int numMagicSquaresInside(vector<vector<int>>& grid) {
int ret = 0;
for(int i=1;i<grid.size()-1;++i){
for(int j=1;j<grid[0].size()-1;++j){
if(judgeSquares(grid,i,j)) ret++;
}
}
return ret;
}
bool judgeSquares(vector<vector<int>>&grid,int i,int j){
set<int>s = {grid[i-1][j-1],grid[i-1][j],grid[i-1][j+1],
grid[i][j-1],grid[i][j],grid[i][j+1],
grid[i+1][j-1],grid[i+1][j],grid[i+1][j+1]};
if(s.size()!=9) return false;
for(auto i:s){
if(i<=0||i>10)return false;
}
return (grid[i][j]==5&&(grid[i-1][j-1]+grid[i-1][j]+grid[i-1][j+1]==15)
&&(grid[i][j-1]+grid[i][j]+grid[i][j+1]==15)
&&(grid[i+1][j-1]+grid[i+1][j]+grid[i+1][j+1]==15)
&&(grid[i-1][j-1]+grid[i][j]+grid[i+1][j+1]==15)
&&(grid[i-1][j+1]+grid[i][j]+grid[i+1][j-1]==15)
&&(grid[i-1][j-1]+grid[i][j-1]+grid[i+1][j-1]==15)
&&(grid[i-1][j]+grid[i][j]+grid[i+1][j]==15)
&&(grid[i-1][j+1]+grid[i][j+1]+grid[i+1][j+1]==15)
);
}
题解:根据描述,第一反应,我们只需要按照他的描述,进一个房间,拿钥匙,再进另一个房间。自然转换成深度优先搜索了。
第二反应,其实就是遍历一遍,看哪些房间不可到达。可用BFS
bool canVisitAllRooms(vector<vector<int>>& rooms) {
int len = rooms.size();
vector<int>visit(len,0);
dfs(rooms,0,visit);
for(auto i:visit){
if(i==0) return false;
}
return true;
}
void dfs(vector<vector<int>>& rooms,int i,vector<int>&visit){
visit[i] = 1;
for(auto room:rooms[i]){
if(!visit[room]) dfs(rooms,room,visit);
}
}