信息学奥赛一本通1329：细胞

信息学奥赛一本通（C++版）在线评测系统

这是一道典型的bfs染色问题，先遍历数组，只要没有标记为1，就开始bfs染色，最后输出color数量

接下来，咱就来把代码拆开来看看：

1. 准备工作，设置地图数组，vis数组，还有bfs的偏移量

char a[11000][11000];  //地图
int vis[110][110];   //记录路径,有没有到过
int dx[4]={0,0,1,-1};  //偏移量
int dy[4]={1,-1,0,0};
int n,m,color=0;  //color染色数
//结构体
struct point{
	int x,y;
};

queue  q;  //bfs队列

2. main函数内部  重点讲讲后面的，先遍历地图，只要找到符合要求的（a不是0），而且没去过（vis是0），就开始bfs广度优先搜索

int main(){
	cin>>n>>m;
	for(int i=0;i>a[i][j];
		}
	}
	for(int i=0;i 
3. 具体bfs函数内部，具体看里面的注释
 
int bfs(int x,int y){
    //基本bfs
	point p;
	p.x=x;
	p.y=y;
	q.push(p);
	while(!q.empty()){  //当队列不为空
		point tmp=q.front();
		q.pop();  //记得pop弹出
		for(int i=0;i<4;i++){
			point np=tmp;
			np.x+=dx[i];  //偏移量
			np.y+=dy[i];
			if(np.x=0 && np.y=0 && vis[np.x][np.y]==0 && a[np.x][np.y]!='0'){
				//假如点坐标合法而且没去过
                q.push(np);
				vis[np.x][np.y]=vis[tmp.x][tmp.y]+1;  //记录步数
			}
		}
	}
	return -1;
}
 
4. 最终ac代码
 
#include 
using namespace std;

char a[11000][11000];
int vis[110][110];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int n,m,color=0;

struct point{
	int x,y;
};

queue  q;
struct point{
	int x,y;
};

queue  q;

int bfs(int x,int y){
	point p;
	p.x=x;
	p.y=y;
	q.push(p);
	while(!q.empty()){
		point tmp=q.front();
		q.pop();
		for(int i=0;i<4;i++){
			point np=tmp;
			np.x+=dx[i];
			np.y+=dy[i];
			if(np.x=0 && np.y=0 && vis[np.x][np.y]==0 && a[np.x][np.y]!='0'){
				q.push(np);
				vis[np.x][np.y]=vis[tmp.x][tmp.y]+1;
			}
		}
	}
	return -1;
}

int main(){
	cin>>n>>m;
	for(int i=0;i>a[i][j];
		}
	}
	for(int i=0;i