当前位置: 代码迷 >> 综合 >> 例题6-12 UVa572 Oil Deposits(DFS)
  详细解决方案

例题6-12 UVa572 Oil Deposits(DFS)

热度:43   发布时间:2024-01-16 13:55:59.0

题意:

就是看有几个可以搜索完的块,求连通块,有个专门的算法名:种子填充

要点:

标准深搜,有上下左右和斜对角的可以用二重循环来表示


#include<stdio.h>
#include<string.h>
#include<stdlib.h>
bool idx[150][150];
char map[150][150];
int m, n;void dfs(int x, int y)
{if (!idx[x][y] || map[x][y] != '@') return;if (x < 0 || x >= m || y < 0 || y >= n)  return;for (int i = -1; i <= 1; i++)for (int j = -1; j <= 1; j++)if (i != 0 || j != 0)     //只要有一个不是0就可以,同时0就不动{map[x][y] = false;dfs(x + i, y + j);}
}int main()
{int i,j;while (scanf("%d%d", &m, &n) != EOF, m + n){memset(idx, true, sizeof(idx));int count = 0;for (i = 0; i < m; i++)scanf("%s", map[i]);for (i = 0; i < m; i++)for (j = 0; j < n; j++){if (idx[i][j] && map[i][j] == '@'){dfs(i, j);count++;}	}printf("%d\n", count);}return 0;
}