練習賽（三）E - Paint the Grid Again

題目鏈接~~>

做題感悟：這題開始讀時感覺很麻煩輸出行列要按優先級，比賽時也沒深入思考。

解題思路：題意就不說了，直接進入主題 ~>? 這題是給你目標狀態，這時你可以從目標狀態倒著推回去把每一步的步驟存起來倒著輸出即可，那要怎樣倒推呢？ 因為你每次都是一行或者一列來處理，你可以把每行每列都單獨拿出來，標記本行或者本列有多少個 ' X ' (行) ，‘ O ' (列)，如果本行的‘ X ' 或者本列的' O ' 已經達到了 n 個 這是你就可以將本行去掉（滿足涂的要求了），然后把本行的” X " 轉化為“ O ” ,或者把本列的“ O ” 轉化為“ X ”( 因為每行每列只能涂一次，so~>如果某個格子被行涂過，那么再一次涂這個格子時必定是涂對應列的時候涂到這個格子，因此需要轉化)。最后如果還存在有的行或者列沒有涂過，就輸出無解。你也可以把本題看成一個 n*n 的棋盤每次涂色相當于向棋盤上放長度為 n 的紙條，目標狀態就是放完所有紙條后的結果，你只要倒著拿完整的紙條就好。

代碼：

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

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) ; // 行在前列在后（因為輸出有優先級）

queueq ;

stacks ;

for(int i=0 ;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

{

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

low[i]++ ;

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

L[top++]=i ;

}

}

else // 列

{

for(int i=0 ;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

{

q.push(L[i]) ;

s.push(L[i]) ;

vis[L[i]]=true ; // 標記已經完成

}

}

bool flag=false ;

for(int i=0 ;i

if(!vis[i])

{

flag=true ;

break ;

}

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

else

{

while(!s.empty())

{

x=s.top() ;

s.pop() ;

if(x

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

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

for(i=0 ;i

{

for(j=0 ;j

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

{

for(j=0 ;j

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 ;

}

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。