从任意的 W 开始,不停地把临接的部分用 ‘ . ’ 代替。1次 DFS 后与初始的这个 W 连接的所有 W 就都被替换成了 ‘ . ’ ,因此直到图中不再存在 W 为止,总共进行 DFS 的次数就是答案了。8个方向共对应了8种状态转移,每个格子作为 DFS 的参数至多被调用一次,所以复杂度为 Ο(8 x N x M) = Ο(N x M)。
for(int dx = -1; dx <= 1; dx++){ for(int dy = -1; dy <= 1; dy++){ int nx = x + dx; int ny = y + dy; if(0 <= nx && nx < N && 0 <= ny && ny < M && field[nx][ny] == 'w') dfs(nx, ny); } } return ; }
voidsolve(){ int res = 0; for(int i = 0; i < N; i++){ for(int j = 0; j < M; j++){ if(field[i][j] == 'w'){ dfs(i, j); res ++; } } } cout << res <<endl; }
intmain(){ cin >> N >> M; for(int i = 0; i < N; i++){ for(int j = 0; j < M; j++){ cin >> field[i][j]; } } solve(); return0; }
If you like this blog or find it useful for you, you are welcome to comment on it. You are also welcome to share this blog, so that more people can participate in it. If the images used in the blog infringe your copyright, please contact the author to delete them. Thank you !
If you like this blog or find it useful for you, you are welcome to comment on it. You are also welcome to share this blog, so that more people can participate in it. If the images used in the blog infringe your copyright, please contact the author to delete them. Thank you !