dfs暴0救助
查看原帖
dfs暴0救助
681349
ShouZheng_Observer楼主2023/4/5 09:50

rt

感觉思路没大问题,但是不知道为啥0分

教练教的 “围一圈法”

球球大佬指点!

#include<bits/stdc++.h>
using namespace std;
const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
long long n,m,ans;
char a[505][505],b[505][505];
bool visited[505][505];
void dfsPre(int x,int y){
	visited[x][y]=true;
	b[x][y]='*';
	for(int i=0;i<4;i++){
		int nx=dx[i]+x,ny=dy[i]+y;
		if(!visited[nx][ny]&&nx>=0&&ny>=0&&nx<=n&&ny<=m&&b[nx][ny]=='0') dfsPre(nx,ny);
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			b[i][j]=a[i][j];
		}
	}
	for(int i=0;i<=n+1;i++) b[i][0]=b[i][n+1]='0';
	for(int j=0;j<=m+1;j++) b[0][j]=b[m+1][j]='0';
	dfsPre(0,0);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if((a[i][j]==b[i][j])&&b[i][j]=='0') ans++;
		}
	}
	cout<<ans;
	return 0;
}

2023/4/5 09:50
加载中...