ZOJ 3781 Paint the Grid Reloaded

题目链接~~>

做题感悟：比赛时最后一个多小时就不淡定了，看哪个哪个不会，处于不断切题状态，那时应该找一个做出来几率大的题思考。

题意：这题就两种颜色，颜色相同且有公共边的（或者通过另一个相同的颜色连接）为一个连通块，如果翻转其中一个，与它在同一个连通块里的都要改变颜色，求达到相同颜色的最小步数。

解题思路：dfs ( 建图) + bfs ( 寻找最优解 ) .

1)  dfs( 建图 ) ,因为翻转的时候每翻转连通块中一个整个连通块都翻转，这样你可以将其看成一个有边相连的无向图，每个边的两个顶点颜色都不一样。

              转化=======〉                

2)  bfs( 寻找最优解 ) , 建完图后就需要翻转计算最优解，可以枚举从每一点开始翻转所得到的最小步数，那怎样寻找最小步数 ？ 假如从 v 这个顶点出发，那么与 v 相邻的顶点颜色必定都与 v 相反，so~> 你只需要把 v的颜色翻转，v与它相邻的所有顶点都是同一个颜色，这时可以把这些顶点看成一个连通块（顶点），再向四周扩展，再次扩展时，周围的颜色必定与此连通块颜色相反，再将它变成与周围顶点相同的颜色，这样又合并成为一个连通块……这样一直进行下去取最大步数。最后从最大步数中取出最小的步数即为最优解。

代码：

      #include<stdio.h>
      #include<iostream>
      #include<map>
      #include<stack>
      #include<string>
      #include<string.h>
      #include<stdlib.h>
      #include<math.h>
      #include<vector>
      #include<queue>
      #include<algorithm>
      using namespace std ;
      const double PI = 3.1415926 ;
      const double esp = 1e-4 ;
      const int  md= 2810778 ;
      const int INF = 999999999 ;
      const int MX = 1625 ;
      int n,m ;
      char s[50][50] ;
      int dx[5]={1,-1,0,0},dy[5]={0,0,1,-1} ;
      int num[50][50] ;  // 用于标记属于哪个集合
      bool vis[MX] ;
      vector<int>G[MX] ;
      struct node
      {
      int x,step ;
      } ;
      int bfs(int x)
      {
      int time=0 ;
      queue<node>q ;
       node curt,next ;
      memset(vis,false,sizeof(vis)) ;
       curt.x=x ;
       curt.step=0 ;
       vis[x]=true ;
       q.push(curt) ;
      while(!q.empty())
       {
       curt=q.front() ;
       q.pop() ;
      if(time<curt.step)
       time=curt.step ;
      int nx=G[curt.x].size() ;
       next.step=curt.step+1 ;
      for(int i=0 ;i<nx ;i++)
       {
       next.x=G[curt.x][i] ;
      if(!vis[next.x])
       {
       vis[next.x]=true ;
       q.push(next) ;
       }
       }
       }
      return  time ;
      }
      bool search(int x,int y)
      {
      if(x<0||y<0||x>=n||y>=m)
      return false ;
      return true ;
      }
      void dfs(int x,int y,int ct,char ch)
      {
      for(int i=0 ;i<4 ;i++)
       {
      int sx=x+dx[i] ;
      int sy=y+dy[i] ;
      if(search(sx,sy))
       {
      if(s[sx][sy]==ch)
       {
      if(num[sx][sy]==-1)
       {
       num[sx][sy]=ct ;
       dfs(sx,sy,ct,ch) ;
       }
       }
      else if(num[sx][sy]!=-1)
       {
      int temp=num[sx][sy] ;
       G[ct].push_back(temp) ; // 建双向边
       G[temp].push_back(ct) ;
       }
       }
       }
      }
      void init() // 初始化
      {
      memset(num,-1,sizeof(num)) ;
      for(int i=0 ;i<n*m ;i++)
       G[i].clear() ;
      }
      int main()
      {
      int Tx,cnt ;
      scanf("%d",&Tx) ;
      while(Tx--)
       {
      scanf("%d%d",&n,&m) ;
       init() ;
       cnt=0 ;
      for(int i=0 ;i<n ;i++)
      scanf("%s",s[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-1,s[i][j]) ;
       }
      int ans=INF ;
      for(int i=0 ;i<cnt ;i++) // 广搜寻找最优解
       {
      int mx=bfs(i) ;
       ans=ans > mx ? mx : ans ;
       }
      printf("%d\n",ans) ;
       }
      return 0 ;
      }
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/24253379