第86场周赛
840. 矩阵中的幻方
题解：根据描述，第一反应，由数据范围，满足题意的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)
);
}841. 钥匙和房间
题解：根据描述，第一反应，我们只需要按照他的描述，进一个房间，拿钥匙，再进另一个房间。自然转换成深度优先搜索了。
第二反应，其实就是遍历一遍，看哪些房间不可到达。可用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);
}
}842. 将数组拆分成斐波那契序列
843. 猜猜这个单词
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-04-132，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录