HDU 1241 Oil Deposits (DFS)
HDU DFS
2023-09-14 09:06:20 时间
题目链接:Oil Deposits
解析:问有多少个“@”块。当中每一个块内的各个“@”至少通过八个方向之中的一个相邻。
直接从“@”的地方開始向相邻八个方向搜索,每搜到一个格子。就将它替换成“.”,一次搜索就会搜索完一个块,记录搜索的次数为答案。
AC代码:
#include <cstdio> #include <cstring> #include <queue> using namespace std; char mz[110][110]; const int dir[8][2] = {0, 1, 1, 0, 0, -1, -1, 0, 1, 1, -1, -1, 1, -1, -1, 1}; //八个方向 int n, m; void dfs(int sx, int sy){ mz[sx][sy] = '.'; //搜到的位置替换成‘.’ for(int i=0; i<8; i++){ int x = sx + dir[i][0]; int y = sy + dir[i][1]; if(x >= 0 && x < n && y >= 0 && y < m && mz[x][y] == '@') dfs(x, y); } return ; } int main(){ // freopen("in.txt", "r", stdin); while(scanf("%d%d", &n, &m) == 2 && n){ for(int i=0; i<n; i++){ scanf("%s", mz[i]); } int ans = 0; for(int i=0; i<n; i++) for(int j=0; j<m; j++){ if(mz[i][j] == '@'){ dfs(i, j); ans ++; //记录搜索次数 } } printf("%d\n", ans); } return 0; }
相关文章
- hdu 1233 还是畅通工程
- 2014 网选 广州赛区 hdu 5025 Saving Tang Monk(bfs+四维数组记录状态)
- HDU 4768 Flyer(二分法)
- 【hdu 6321】Dynamic Graph Matching
- 【35.43%】【hdu 4347】The Closest M Points
- (hdu 简单题 128道)平方和与立方和(求一个区间的立方和和平方和)
- hdu 2899 hdu 3400 三分/几何
- HDU 1711 Number Sequence(kmp)
- HDU 3172 Virtual Friends(并用正确的设置检查)
- hdu 4445 Crazy Tank (暴力枚举)
- hdu 4828 Grids(拓展欧几里得+卡特兰数)
- HDU 4497 GCD and LCM (分解质因数)
- HDU 3313 Key Vertex(dfs + bfs)
- 刷题记录:HDU - 3001Travelling