Onway

我是一只菜菜菜菜鸟...
posts - 61, comments - 56, trackbacks - 0, articles - 34

pku 1315 回溯法

Posted on 2010-12-17 10:10 Onway 阅读(350) 评论(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;
}

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理