练习赛（三）E - Paint the Grid Again

题目链接~~>

做题感悟：这题开始读时感觉很麻烦输出行列要按优先级，比赛时也没深入思考。

解题思路：题意就不说了，直接进入主题 ~>  这题是给你目标状态，这时你可以从目标状态倒着推回去把每一步的步骤存起来倒着输出即可，那要怎样倒推呢？ 因为你每次都是一行或者一列来处理，你可以把每行每列都单独拿出来，标记本行或者本列有多少个 ' X ' (行) ，‘ O ' (列)，如果本行的‘ X ' 或者本列的' O ' 已经达到了 n 个 这是你就可以将本行去掉（满足涂的要求了），然后把本行的” X " 转化为“ O ” ,或者把本列的“ O ” 转化为“ X ”( 因为每行每列只能涂一次，so~>如果某个格子被行涂过，那么再一次涂这个格子时必定是涂对应列的时候涂到这个格子，因此需要转化)。最后如果还存在有的行或者列没有涂过，就输出无解。你也可以把本题看成一个 n*n 的棋盘每次涂色相当于向棋盘上放长度为 n 的纸条，目标状态就是放完所有纸条后的结果，你只要倒着拿完整的纸条就好。

代码：

  

   

    

     

    
    

     

      #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 ;
     
    
   

    

     

    
    

     

      #define lld __int64
     
    
   

    

     

    
    

     

      const double PI = 3.1415926 ;
     
    
   

    

     

    
    

     

      const double esp = 1e-4 ;
     
    
   

    

     

    
    

     

      const int  md= 2810778 ;
     
    
   

    

     

    
    

     

      const int INF = 999999999 ;
     
    
   

    

     

    
    

     

      const int MX = 1005 ;
     
    
   

    

     

    
    

     

      int top,n ;
     
    
   

    

     

    
    

     

      bool vis[MX*2] ; 
     
    
   

    

     

    
    

     

      int row[MX],low[MX] ;
     
    
   

    

     

    
    

     

      char sx[MX][MX] ;
     
    
   

    

     

    
    

     

      int L[MX] ;
     
    
   

    

     

    
    

     

      bool cmp(int a,int b)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 return a > b ? a : b ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void search()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       sort(L,L+top,cmp) ; // 行在前列在后（因为输出有优先级）
     
    
   

    

     

    
    

     
 queue<int>q ;
     
    
   

    

     

    
    

     
 stack<int>s ;
     
    
   

    

     

    
    

     
 for(int i=0 ;i<top ;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       q.push(L[i]) ;
     
    
   

    

     

    
    

     

       s.push(L[i]) ;
     
    
   

    

     

    
    

     

       vis[L[i]]=true ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 int x ;
     
    
   

    

     

    
    

     
 while(!q.empty())
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       top=0 ;
     
    
   

    

     

    
    

     

       x=q.front() ;
     
    
   

    

     

    
    

     

       q.pop() ;
     
    
   

    

     

    
    

     
 if(x>=n)  // 行
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       x-=n ;
     
    
   

    

     

    
    

     
 for(int i=0 ;i<n ;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       sx[x][i]='O' ;
     
    
   

    

     

    
    

     

       low[i]++ ;
     
    
   

    

     

    
    

     
 if(low[i]==n&&!vis[i])
     
    
   

    

     

    
    

     

       L[top++]=i ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else // 列
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 for(int i=0 ;i<n ;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       sx[i][x]='X' ;
     
    
   

    

     

    
    

     

       row[i]++ ;
     
    
   

    

     

    
    

     
 if(row[i]==n&&!vis[i+n])
     
    
   

    

     

    
    

     

       L[top++]=i+n ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       sort(L,L+top,cmp) ;
     
    
   

    

     

    
    

     
 for(int i=0 ;i<top ;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       q.push(L[i]) ;
     
    
   

    

     

    
    

     

       s.push(L[i]) ;
     
    
   

    

     

    
    

     

       vis[L[i]]=true ;  // 标记已经完成
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 bool flag=false ;
     
    
   

    

     

    
    

     
 for(int i=0 ;i<n*2 ;i++)
     
    
   

    

     

    
    

     
 if(!vis[i])
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       flag=true ;
     
    
   

    

     

    
    

     
 break ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(flag)  printf("No solution\n") ; // 输出
     
    
   

    

     

    
    

     
 else
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 while(!s.empty())
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       x=s.top() ;
     
    
   

    

     

    
    

     

       s.pop() ;
     
    
   

    

     

    
    

     
 if(x<n) printf("C") ;
     
    
   

    

     

    
    

     
 else
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 printf("R") ;
     
    
   

    

     

    
    

     

       x-=n ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 printf("%d",x+1) ;
     
    
   

    

     

    
    

     
 while(!s.empty())
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 printf(" ") ;
     
    
   

    

     

    
    

     
 break ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 printf("\n") ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void init() // 初始化
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       top=0 ;
     
    
   

    

     

    
    

     
 memset(row,0,sizeof(row)) ;
     
    
   

    

     

    
    

     
 memset(low,0,sizeof(low)) ;
     
    
   

    

     

    
    

     
 memset(vis,false,sizeof(vis)) ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int Tx,i,j ;
     
    
   

    

     

    
    

     
 scanf("%d",&Tx) ;
     
    
   

    

     

    
    

     
 while(Tx--)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%d",&n) ;
     
    
   

    

     

    
    

     

       init() ;
     
    
   

    

     

    
    

     
 for(i=0 ;i<n ;i++)
     
    
   

    

     

    
    

     
 scanf("%s",sx[i]) ; 
     
    
   

    

     

    
    

     
 for(i=0 ;i<n ;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 for(j=0 ;j<n ;j++) // 统计一行有多少个 X 行用 n-1~n*2-1 表示
     
    
   

    

     

    
    

     
 if(sx[i][j]=='X')
     
    
   

    

     

    
    

     

       row[i]++ ;
     
    
   

    

     

    
    

     
 if(row[i]==n)
     
    
   

    

     

    
    

     

       L[top++]=i+n ;
     
    
   

    

     

    
    

     
 else if(!row[i])  vis[i+n]=true ;  
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 for(i=0 ;i<n ;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 for(j=0 ;j<n ;j++) // 统计一列由多少个 O 列用 n ~ 2*n-1 表示
     
    
   

    

     

    
    

     
 if(sx[j][i]=='O')
     
    
   

    

     

    
    

     

       low[i]++ ;
     
    
   

    

     

    
    

     
 if(low[i]==n)
     
    
   

    

     

    
    

     

       L[top++]=i ;
     
    
   

    

     

    
    

     
 else if(!low[i])  vis[i]=true ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(top) 
     
    
   

    

     

    
    

     

       search() ;
     
    
   

    

     

    
    

     
 else printf("No solution\n") ;// 如果不存在完整的行||列
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

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

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