蒟蒻求问 dfs
  • 板块学术版
  • 楼主松毛虫
  • 当前回复4
  • 已保存回复4
  • 发布时间2021/9/5 17:21
  • 上次更新2023/11/4 07:38:17
查看原帖
蒟蒻求问 dfs
108881
松毛虫楼主2021/9/5 17:21
#include<iostream>
#include<cstring>
#define maxn 102
#define smc 0
using namespace std;
int walk[8][2] = {{1,0}, {0,1}, {-1,1}, {1,-1}, {-1,-1}, {0,-1}, {-1,0}, {1,1}};
int n, m, ans = 1;
char map[maxn][maxn];
bool vis[maxn][maxn];
void dfs(int x, int y){
	if(x < 0 || x >= n || y < 0 || y >= m || map[x][y] == '.' || vis[x][y] != 0) return;
	map[x][y] = '.', vis[x][y] = ans;
	for(int i = 0;i < 8;i++) dfs(x + walk[i][0], y + walk[i][1]);
}
int main(){
	memset(vis, 0, sizeof(vis));
	cin>>n>>m;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			cin>>map[i][j];
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++){
			if(map[i][j] == 'W'){
				dfs(i, j); ans++;
			}
		}
	cout<<ans - 1;
	return 0;
}

这是https://www.luogu.com.cn/problem/P1596 的AC代码 答案是正确(33)的

if(x < 0 || x > n || y < 0 || y > m || map[x][y] == '.' || vis[x][y] != 0) return;

但是边界判断之前写错了,是这个样的。输出的答案是22,但是我输入的样例

10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

如果越界的话,为什么会答案会变成2呢 求神犇解答storz

2021/9/5 17:21
加载中...