hdu 1045 贪心回溯(二)
2014-11-24 11:48:54
·
作者:
·
浏览: 4
; } void dfs(int pos,int sum) { int r=pos/n,c=pos%n;//计算所检查的位置 printf("pos=%d sum=%d r=%d c=%d \t",pos,sum,r,c); if(pos==n*n){//什么意思呢，感觉pos永远不会和n*n相等阿 if(sum>ans)//会的，这样会把当前的活动点干死，执行这句dfs(pos+1,sum) ans=sum; return ; } if(map[r][c]=='.'){ if(check(r,c)==1){//符合题目要求的话 map[r][c]='b';//表示建立一个blockhouse dfs(pos+1,sum+1);//向下寻找，同时sum+1 map[r][c]='.';//这里我就不懂了，为什么要添加这一步哪 printf("2r=%d 2pos=%d sum=%d\n",r,pos,sum);//有大用，这句话是回溯时恢复原来的状态 } } dfs(pos+1,sum);//只是pos移动，其他没有变化 //printf("pos=%d sum=%d\t",r,c); } int main() { freopen("in.txt","r",stdin); int i; while(scanf("%d",&n),n){ ans=0; memset(map,0,sizeof(map)); for(i=0;i
>map[i]; dfs(0,0); printf("%d\n",ans); } }
中间过程数据；
pos=0 sum=0 r=0 c=0 pos=1 sum=1 r=0 c=1 pos=2 sum=1 r=1 c=0 pos=3 sum=1 r=1 c=1 pos=4 sum=2 r=2 c=0 2r=1 2pos=3 sum=1
pos=4 sum=1 r=2 c=0 2r=0 2pos=0 sum=0
pos=1 sum=0 r=0 c=1 pos=2 sum=1 r=1 c=0 pos=3 sum=2 r=1 c=1 pos=4 sum=2 r=2 c=0 2r=1 2pos=2 sum=1
pos=3 sum=1 r=1 c=1 pos=4 sum=1 r=2 c=0 2r=0 2pos=1 sum=0
pos=2 sum=0 r=1 c=0 pos=3 sum=1 r=1 c=1 pos=4 sum=1 r=2 c=0 2r=1 2pos=2 sum=0
pos=3 sum=0 r=1 c=1 pos=4 sum=1 r=2 c=0 2r=1 2pos=3 sum=0
pos=4 sum=0 r=2 c=0 2