首页 > 代码库 > Paint the Grid Reloaded（缩点，DFS+BFS）
Paint the Grid Reloaded（缩点，DFS+BFS）
Leo has a grid with N rows and M columns. All cells are painted with either black or white initially.
Two cells A and B are called connected if they share an edge and they are in the same color, or there exists a cell C connected to both A and B.
Leo wants to paint the grid with the same color. He can make it done in multiple steps. At each step Leo can choose a cell and flip the color (from black to white or from white to black) of all cells connected to it. Leo wants to know the minimum number of steps he needs to make all cells in the same color.
Input
There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:
The first line contains two integers N and M (1 <= N, M <= 40). Then N lines follow. Each line contains a string with N characters. Each character is either ‘X‘ (black) or ‘O‘ (white) indicates the initial color of the cells.
Output
For each test case, output the minimum steps needed to make all cells in the same color.
Sample Input
22 2OXOX3 3XOXOXOXOX
Sample Output
12
Hint
For the second sample, one optimal solution is:
Step 1. flip (2, 2)
XOXOOOXOX
Step 2. flip (1, 2)
XXXXXXXXX
/*题意：给你一个只有元素O/X的矩阵，有这样一种操作每次你点一个元素的时候，这个元素所在的联通块(颜色相同)就会翻转， 问你最少经过几次操作可以将所有的元素变成颜色统一初步思路：很隐含的最长路，先找出所有的联通块，将相邻的联通块进行建边，枚举从每一个点开始的最长路，就是从这个点 开始翻需要的最小操作，因为相邻的联通块只需要一次操作就可以变成相同的颜色。*/#include <bits/stdc++.h>#define ll long long#define INF 0x3f3f3f3f#define pb push_backusing namespace std;struct node{ int x,step; node(){} node(int a,int b):x(a),step(b){}};int t;int n,m;char mapn[45][45];int num[45][45];//表示所在的联通块int cnt;//表示联通块的数量int dir[4][2]={1,0,-1,0,0,1,0,-1};int minstep;int judge[1605][1605];//判断是不是建了重边vector<int> edge[1605];bool ok(int x,int y){ if(x<0||x>=n||y<0||y>=m) return false; return true;}void dfs(int x,int y,int cur,char op){ for(int i=0;i<4;i++){ int fx=x+dir[i][0]; int fy=y+dir[i][1]; if(ok(fx,fy)==false) continue; if(mapn[fx][fy]==op){//是一个联通块的 if(num[fx][fy]==-1){//如果他还没有被标记 num[fx][fy]=cur; dfs(fx,fy,cur,op); } }else{//如果不是一个联通块的那么就要建边了 if(num[fx][fy]!=-1){//建双向边 if(!judge[cur][num[fx][fy]]){ edge[cur].pb(num[fx][fy]); edge[num[fx][fy]].pb(cur); judge[cur][num[fx][fy]]=1; judge[num[fx][fy]][cur]=1; } } } }}int bfs(int x){ int vis[1605]; memset(vis,0,sizeof vis); node start(x,0),Next; vis[x]=1; queue<node>q; int times=0; q.push(start); while(!q.empty()){ Next=q.front(); q.pop(); // cout<<Next.x<<endl; if(Next.step>times){ times=Next.step; } for(int i=0;i<edge[Next.x].size();i++){ int v=edge[Next.x][i]; if(v==Next.x) continue;//防止死循环 if(!vis[v]){ q.push(node(v,Next.step+1)); vis[v]=1; } } } return times;}void init(){ cnt=0; memset(num,-1,sizeof num); memset(judge,0,sizeof judge); for(int i=0;i<1605;i++){ edge[i].clear(); } minstep=2000;}int main(){ // freopen("in.txt","r",stdin); scanf("%d",&t); while(t--){ init(); scanf("%d%d",&n,&m); for(int i=0;i<n;i++){ scanf("%s",mapn[i]); }//输入 for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(num[i][j]==-1){ num[i][j]=++cnt; dfs(i,j,cnt,mapn[i][j]); } } }//寻找联通块进行建边 for(int i=1;i<=cnt;i++){ // cout<<"i="<<i<<endl; int tmp=bfs(i); // cout<<tmp<<endl; minstep=min(minstep,tmp); } printf("%d\n",minstep); } return 0;}
Paint the Grid Reloaded（缩点，DFS+BFS）