DFS样例已过,WA,TLE
查看原帖
DFS样例已过,WA,TLE
666682
songsonghui楼主2022/3/2 18:01
#include <iostream>
#include <cstring>
int n,m,x,y;
char map[1005][1005];
int ans[100005];
bool visited[1005][1005] = {false};
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};
bool check(int x,int y){
	if(x<1 ||x>n||y<1||y>m) return false;
	if(visited[x][y]) return false;
	return true;
} 
int dfs(int x, int y,int num){
	visited[x][y] = true;
//	printf("(%d,%d)\n",x,y);
	for(int i =0;i<4;i++){
		int nx = x + dx[i],ny = y + dy[i];
		if(check(nx,ny) && map[nx][ny]!=map[x][y]){
			num+=dfs(nx,ny,1);
		}
	}
	//visited[x][y] = false;
	return num;
}

int main(int argc, char** argv) {
	int j =0;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%s",map[i] + 1);
	}
	for(int i =1;i<=m;i++){
		scanf("%d%d",&x,&y);
		memset(visited,false,sizeof(visited));
		int num = dfs(x,y,1);
		ans[j++] = num;
	}
	for(int i = 0;i<m;i++) printf("%d\n",ans[i]);
	return 0;
	
}
2022/3/2 18:01
加载中...