信息学奥赛一本通(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; }; queueq; //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代码
#includeusing 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