BFS 30分求调
查看原帖
BFS 30分求调
349592
轮回·天照楼主2022/5/14 12:22
#include <bits/stdc++.h>
using namespace std;
int n,m,ans = 0;
int dir[4][2] = {0,1,0,-1,1,0,-1,0};
char mp[1000][1000];
int vis[1000][1000];
void dfs(int x,int y){
	for(int i = 0;i < 4;i++){
		int tx = x + dir[i][0];
		int ty = y + dir[i][1];
		if(tx < 1 || tx > n + 1 || ty < 1 || ty > m + 1 || vis[tx][ty] || mp[tx][ty] == '*')
			continue;
		vis[tx][ty] = 1;
		mp[tx][ty] = '*';
		dfs(tx,ty);
	}
}
int main(){
    cin >> n >> m;
    for(int i = 1;i <= n;i++)
    	for(int j = 1;j <= m;j++)
    		cin >> mp[i][j];
    for(int j = 1;j <= m;j++){
		if(mp[1][j] == '0'){
			mp[1][j] = '*';
			vis[1][j] = 1;
			dfs(1,j);
			vis[1][j] = 0;
		}
	}
	for(int i = 2;i < n;i++){
		if(mp[i][1] == '0'){
			mp[i][1] = '*';
			vis[i][1] = 1;
			dfs(i,1);
			vis[i][1] = 0;
		}
		if(mp[i][n] == '0'){
			mp[i][n] = '*';
			vis[i][n] = 1;
			dfs(i,n);
			vis[i][n] = 0;
		}
	}
	for(int j = 1;j <= m;j++){
		if(mp[n][j] == '0'){
			mp[n][j] = '*';
			vis[n][j] = 1;
			dfs(n,j);
			vis[n][j] = 0;
		}
	}
	for(int i = 1;i <= n;i++)
    	for(int j = 1;j <= m;j++)
    		if(mp[i][j] == '0')
				ans++;
    cout << ans << endl;
    return 0;
}

只有#4 #7 #10过了

2022/5/14 12:22
加载中...