递归+回朔,超级好的题目ZOJ1002/HDU1045

原创文章,转载请注明出处.转载自: Li Haifeng's Blog
本文链接地址: 递归+回朔,超级好的题目ZOJ1002/HDU1045



1、棋盘问题,如果要用递归,最好是用一维数组来传递参数。
2、注意截止条件的运用。
3、剪枝条件很明显,但是很多,不能出错



Problem : 1045 ( Fire Net )      Judge Status : Accepted
RunId : 1346734     Language : C++     Author :
05xiaofendui
Code Render Status : Rendered By HDOJ C++ Code Rander Version 0.01 Bet




#include<iostream>

using namespace
std;

int
n;//实际上棋盘的规模
int FinalCount=0;
int
map[4][4]={0};/*0 自由状态,1 已经住人 ,-1 是墙*/
int
panduan(int row,int col)
{

int
left_i,right_i,up_i,down_i;
//先向左看
int temp_row=row;
int
temp_col=col;
for
(left_i=1;left_i<n&&temp_col>0;left_i++)
{

temp_col--;
if
(map[temp_row][temp_col]==-1)
break
;//这边就不用再看了
else if(map[temp_row][temp_col]==1)
return
0;//这个方向有人了,不要再探索了

}

temp_col=col;
for
(right_i=1;right_i<n&&temp_col<n-1;right_i++)
{

temp_col+=1;
if
(map[temp_row][temp_col]==-1)
break
;//这边就不用再看了
else if(map[temp_row][temp_col]==1)
return
0;//这个方向有人了,不要再探索了

}

temp_col=col;
temp_row=row;
for
(up_i=1;up_i<n&&temp_row>0;up_i++)
{

temp_row-=1;
if
(map[temp_row][temp_col]==-1)
break
;//这边就不用再看了
else if(map[temp_row][temp_col]==1)
return
0;//这个方向有人了,不要再探索了

}

temp_col=col;
temp_row=row;
for
(down_i=1;down_i<n&&temp_row<n-1;down_i++)
{

temp_row+=1;
if
(map[temp_row][temp_col]==-1)
break
;//这边就不用再看了
else if(map[temp_row][temp_col]==1)
return
0;//这个方向有人了,不要再探索了

}

return
1;
}

void
Judge(int num,int Count)
{

int
col=num%n;
int
row=num/n;
if
(num==n*n)//到达最后的状态+1
{
if
(FinalCount<Count)
FinalCount=Count;//这样子就赋值
return ;
}


if
(map[row][col]==0&&panduan(row,col))
{

map[row][col]=1;//放人
Judge(num+1,Count+1);
map[row][col]=0;
}

Judge(num+1,Count);//如果这个地方不可以放人的话,就看下一个位置
}
int
main()
{

while
(cin>>n&&n!=0)
{

memset(map,0,sizeof(map));
int
i,j;
FinalCount=0;
for
(i=0;i<n;i++)
for
(j=0;j<n;j++)
{

char
c;
cin>>c;
if
(c=='.')
map[i][j]=0;
else

map[i][j]=-1;
}

Judge(0,0);
cout<<FinalCount<<endl;

}

return
1;
}


From Li Haifeng's Blog, post 递归+回朔,超级好的题目ZOJ1002/HDU1045

Post Footer automatically generated by wp-posturl plugin for wordpress.

分享到: