ural 1250

本文主要是介绍ural 1250，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

有点坑的dfs  看懂题应该就会做了 神圣海必然围成一个圈  dfs将神圣还外围的全部去掉   简单题 

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
int dx[] = {1, 1, 1, -1, -1, -1, 0, 0};
int dy[] = {1, 0, -1, 0, 1, -1, 1, -1};
int ex[] = {1, -1, 0, 0};
int ey[] = {0, 0, 1, -1};
int g[510][510],w,h;
bool ok(int x, int y)
{if(x >= 1 && y >= 1 && x <= h && y <= w)return true;return false;
}
void dfs1(int x, int y)
{if(g[x][y] == 1){g[x][y] = 2;for(int i = 0; i < 8; i++){int nx = x+dx[i], ny = y+dy[i];if(ok(nx,ny))dfs1(nx, ny);}}
}
void dfs2(int x, int y)
{if(g[x][y] != 2 && g[x][y] != 3){g[x][y] = 3;for(int i = 0; i < 4; i++){int nx = x+ex[i], ny = y+ey[i];if(ok(nx,ny))dfs2(nx, ny);}}
}
void dfs3(int x, int y)
{if(g[x][y] == 0){g[x][y] = 1;for(int i = 0; i < 4; i++){int nx = x+ex[i], ny = y+ey[i];if(ok(nx,ny))dfs3(nx, ny);}}
}
int main()
{int x,y;char c;scanf("%d%d%d%d",&w,&h,&x,&y);getchar();memset(g, 0, sizeof(g));for(int i = 1; i <= h; i++){for(int j = 1; j <= w; j++){scanf("%c",&c);if(c == '.')g[i][j] = 1;}getchar();}dfs1(y, x);for(int i = 1; i <= w; i++){if(g[1][i] != 2)dfs2(1, i);if(g[h][i] != 2)dfs2(h, i);}for(int i = 1; i <= h; i++){if(g[i][1] != 2)dfs2(i, 1);if(g[i][w] != 2)dfs2(i, w);}int ans = 0;for(int i = 1; i <= h; i++)for(int j = 1; j <= w; j++){if(!g[i][j]){dfs3(i, j);ans++;}}printf("%d\n",ans);return 0;
}

这篇关于ural 1250的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---