【题目标题】拯救小码君

【算法分析】

本题是经典的Flood Fill，即洪水填充问题，只需输出‘0’的连通块个数，可以用dfs算法。本题需要额外减去边界的'0'的连通块。

【参考代码】

#include<bits/stdc++.h>
using namespace std;

int ans;
char mp[505][505]; 
int vis[505][505];  //表示是否被访问过 
int dir[4][2] = {   //进行位置变换 
	{0,1},{1,0},{0,-1},{-1,0}
};
int n,m;

bool in(int x,int y){ 
	return x >= 0 && y >= 0 && x < n && y < m;
}

void dfs(int x,int y,int add){ //add表示是否要算进没被淹没的0 
	ans += add;
	vis[x][y] = 1;
	int dx,dy;
	for(int i = 0;i < 4;i++){
		dx = x + dir[i][0];
		dy = y + dir[i][1];
		if(in(dx,dy) && mp[dx][dy] == '0' && !vis[dx][dy]) 
			dfs(dx,dy,add);
	}
}

int main(){
	cin >> n >> m;
	for(int i = 0;i < n;i++){
		cin >> mp[i];
	}
	
	for(int i = 0;i < n;i++){  //根据题意，边界上的0一定会被淹没 
		for(int j = 0;j < m;j++){
			if(((i == 0) || (i == n - 1) || (j == 0) || (j == m - 1)) && (mp[i][j] == '0')) 
				dfs(i,j,0);
		}
	}
	
	for(int i = 0;i < n;i++){
		for(int j = 0;j < m;j++){
			if(mp[i][j] == '0' && !vis[i][j]) { 
				dfs(i,j,1);
			}
		}
	}
	
	cout << ans;
} 

【时间复杂度】

$O(nm)$

【预计分数】

100pts