Posted on 2010-12-17 10:10
Onway 閱讀(378)
評論(0) 編輯 收藏 引用 所屬分類:
傷不起的ACM
/*************************************************************************
*pku 1315 Don't Get Rooked
http://poj.org/problem?id=1315
題目分類：回溯法
題意：n*n的棋盤，類似n后問題，橫豎不能放兩個棋子，不同的是，少了\
對角線的限制，棋盤里多了分割橫行和豎行的墻。求最多能放棋子數(shù)。
思路：枚舉第一個棋子的位子，確定第一個棋子位置后，對后面的棋子用\
遞歸深搜（即回溯法）暴力求解剩下能放的棋子。題目的難點是進入深搜時\
的標(biāo)記和回溯時撤銷標(biāo)記的操作。
代碼附注：近段時間比較少做題，在標(biāo)記操作里調(diào)試了很久，最后還感覺\
改得挺惡心的，代碼很臃腫。但交上去居然0MS一次AC了，也有借口不改進了。
**************************************************************************/
#include <iostream>
using namespace std;
char board[5][5];
int record[5][5];
int sum,tmp,n;
int code=0;
void rec(int ,int);
int main()
{
while(cin>>n&&n)
{
memset(record,-1,sizeof(record));
int i,j;
for(i=0;i<n;++i)
cin>>board[i];
sum=0;tmp=0;
for(i=0;i<n;++i)
for(j=0;j<n;++j)
{
if(board[i][j]!='X')
rec(i,j);
}
cout<<sum<<endl;
}
return 0;
}
void sign(int i,int j)
{
int k;
for(k=i-1;k>=0;--k)
if(board[k][j]=='X') break;
else if(board[k][j]=='.')
{board[k][j]='u';record[k][j]=code;}
for(k=i+1;k<n;++k)
if(board[k][j]=='X') break;
else if(board[k][j]=='.')
{board[k][j]='u';record[k][j]=code;}
for(k=j-1;k>=0;--k)
if(board[i][k]=='X') break;
else if(board[i][k]=='.')
{board[i][k]='u';record[i][k]=code;}
for(k=j+1;k<n;++k)
if(board[i][k]=='X') break;
else if(board[i][k]=='.')
{board[i][k]='u';record[i][k]=code;}
}
void reset(int i,int j)
{
int k;
for(k=i-1;k>=0;--k)
if(board[k][j]=='X') break;
else if(board[k][j]=='u'&&record[k][j]==code)
{board[k][j]='.';record[k][j]=-1;}
for(k=i+1;k<n;++k)
if(board[k][j]=='X') break;
else if(board[k][j]=='u'&&record[k][j]==code)
{board[k][j]='.';record[k][j]=-1;}
for(k=j-1;k>=0;--k)
if(board[i][k]=='X') break;
else if(board[i][k]=='u'&&record[i][k]==code)
{board[i][k]='.';record[i][k]=-1;}
for(k=j+1;k<n;++k)
if(board[i][k]=='X') break;
else if(board[i][k]=='u'&&record[i][k]==code)
{board[i][k]='.';record[i][k]=-1;}
}
void rec(int i,int j)
{
++tmp;
++code;
board[i][j]='r';
sign(i,j);
for(int row=i;row<n;++row)
{
int col;
if(row==i) col=j+1;
else col=0;
for(;col<n;++col)
{
if(board[row][col]=='.')
rec(row,col);
}
}
if(sum<tmp) sum=tmp;
reset(i,j);
board[i][j]='.';
--code;
--tmp;
}