Posted on 2010-12-17 10:10
Onway 阅读(351)
评论(0) 编辑 收藏 引用 所属分类:
伤不起的ACM
/*************************************************************************
*pku 1315 Don't Get Rooked
http://poj.org/problem?id=1315
题目分类：回溯法
题意：n*n的棋盘，类似n后问题，横竖不能放两个棋子，不同的是，少了\
对角线的限制，棋盘里多了分割横行和竖行的墙。求最多能放棋子数。
思路：枚举第一个棋子的位子，确定第一个棋子位置后，对后面的棋子用\
递归深搜（即回溯法）暴力求解剩下能放的棋子。题目的难点是进入深搜时\
的标记和回溯时撤销标记的操作。
代码附注：近段时间比较少做题，在标记操作里调试了很久，最后还感觉\
改得挺恶心的，代码很臃肿。但交上去居然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;
}