本文主要是介绍zoj3781 Paint the Grid Reloaded --- 缩点 bfs，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
╮(╯▽╰)╭水题
相连的相同色块缩成点，和相邻的不同色块建边。
以每一个点为起点bfs，求最小答案。
题意：
给一个n*m的X O构成的格子（其实给的是n*n，但处理时都当做n*m，真是奇怪啊），对一个点操作可以使与它相连通的所有一样颜色的格子翻转颜色（X—>O或O—>X），问给定的矩阵最少操作多少次可以全部变成一样的颜色。
思路：
每次操作都将本身所在的连通块与和自己相邻的不同颜色的连通块变成同一种颜色，也就是变成一个连通块了，那么要使n次操作后全部变成一样的颜色，也就是从某点出发到达其余所有点。
dfs把连通块缩成点，然后相邻的连通块之间建边，枚举以每个点为根的情况，bfs求出每种情况的深度，取最小的即为答案。
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define inf 0x3f3f3f3f
#define ll long long
#define mod 1000000007
using namespace std;char mp[45][45];
int num[1610],cnt,n,m,vis[1610];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
vector<int> v[1600];struct node
{int d,id;
};void dfs(int x,int y,int no,char c)
{int i,xx,yy,tmp;for(i=0;i<4;i++){xx=x+dx[i];yy=y+dy[i];if(xx<0||xx>=n||yy<0||yy>=m) continue;if(mp[xx][yy]==c){if(num[xx*m+yy]==-1)//没有搜过的连通点{num[xx*m+yy]=no;dfs(xx,yy,no,c);}}else if(num[xx*m+yy]!=-1)//没有搜过的相邻不同颜色的点{tmp=num[xx*m+yy];v[no].push_back(tmp);v[tmp].push_back(no);}}
}int bfs(int no)
{queue<node> q;node tmp,now;tmp.d=0;tmp.id=no;q.push(tmp);int ret=0;memset(vis,0,sizeof vis);vis[tmp.id]=1;while(!q.empty()){now=q.front();q.pop();if(ret<now.d) ret=now.d;tmp.d=now.d+1;for(int j=0;j<v[now.id].size();j++){tmp.id=v[now.id][j];if(!vis[tmp.id]){vis[tmp.id]=1;q.push(tmp);}}}return ret;
}int main()
{int t,i,j,ans;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);for(i=0;i<n;i++)scanf("%s",mp[i]);for(i=0;i<=n*m;i++)v[i].clear();memset(num,-1,sizeof num);cnt=0;for(i=0;i<n;i++){for(j=0;j<m;j++){if(num[i*m+j]==-1){num[i*m+j]=cnt;dfs(i,j,cnt,mp[i][j]);cnt++;}}}ans=inf;for(i=0;i<cnt;i++)ans=min(ans,bfs(i));printf("%d\n",ans);}return 0;
}
这篇关于zoj3781 Paint the Grid Reloaded --- 缩点 bfs的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
