wordpress中文版安装教程,网站seo优化查询,免费漫画网站,动画小视频制作神器首先拿到这道题不要想着去直接判断环里面的岛屿#xff0c;这样太困难了#xff0c;我们可以使用之前做过的题的经验#xff0c;在输入加入一圈海水#xff0c;然后从(0,0)点开始BFS#xff0c;这里进行八向搜索#xff0c;搜到的0全部都染色成2#xff0c;假如2能够蔓延… 首先拿到这道题不要想着去直接判断环里面的岛屿这样太困难了我们可以使用之前做过的题的经验在输入加入一圈海水然后从(0,0)点开始BFS这里进行八向搜索搜到的0全部都染色成2假如2能够蔓延到岛屿的周围就说明这个岛屿不在环里面因为从外面无法蔓延到环里面。
在经历了染色过程之后我们就可以直接BFS搜索岛屿了搜到任何被2围绕的岛屿就让答案加1。
代码
#includeiostream
#includequeue
#includecstring
using namespace std;
const int N 55;
const int dx[4] { 1,0,-1,0 };
const int dy[4] { 0,1,0,-1 };
const int ddx[8] { 1,1,0,0,-1,-1,1,-1 };
const int ddy[8] { 1,-1,1,-1,1,-1,0,0 };char g[N][N];
int n, m;
bool vis[N][N];
int res 0;void bfs(int ix, int iy, int st) {bool flag 0; //标记周围是否有2queuepairint, intq;q.push({ ix,iy });vis[ix][iy] 1;while (q.size()) {auto t q.front(); q.pop();if (st 1) { //这里是搜索岛屿的过程for (int i 0; i 4; i) {int x t.first dx[i], y t.second dy[i];if (x 1 x n y 1 y m !vis[x][y]) {if (g[x][y] 2)flag 1;if (g[x][y] 1) {q.push({ x,y });vis[x][y] 1;}}}}else { //这里是搜索外围海洋的过程for (int i 0; i 8; i) {int x t.first ddx[i], y t.second ddy[i];if (x 0 x n 1 y 0 y m 1 !vis[x][y] g[x][y] 0) {q.push({ x,y });g[x][y] 2;vis[x][y] 1;}}}}if (flag)res; //如果不在环里面答案加1
}int main() {int t; cin t;while (t--) {memset(vis, 0, sizeof vis); //初始化memset(g, 0, sizeof g);cin n m;for (int i 1; i n; i) {for (int j 1; j m; j) {cin g[i][j];}}bfs(0, 0, 2);memset(vis, 0, sizeof vis); //搜完一遍海洋之后也要初始化res 0;for (int i 1; i n; i) {for (int j 1; j m; j) {if (g[i][j] 1 !vis[i][j]) {bfs(i, j, 1);}}}cout res endl;}return 0;
}
