（回溯）ZOJ1002 Fire Net

忘是亡心i 2022-04-12 02:49 173阅读 0赞

传送门： [ZOJ1002 Fire Net][]

哈哈哈，其实这道题目只是八皇后题目的简单变形，一开始，感觉自己做不上来，就直接搜答案。看了几个题解，感觉写得很复杂，也不想看。于是，自己独立试着分析，不出半个小时就做完啦，，，

好了，不啰嗦啦~直接说思路吧

回溯其实就是搜索式的枚举，对于一行中的每一列，如果这个位置是'.'且它的前面和它的左边没有放房子（如果有个墙挡住了你的实现，导致你没看到墙后面放置的房子，这种情况也可以算作它的前面和它的左边没有放房子），那么咱们就可以在这里放一个房子。当然也可以不放，不放的话就把标记都恢复。最后，这一行也选择这一行都不放房子，直接去下一行继续试探~

**代码：**

#include <iostream>
    #include <cstdio>
    #include <cstring>
    using namespace std;
    int vx[5],vy[5];  //vx[]行标记，vy[]列标记
    int ans,n;
    char mp[5][5];
    
    void dfs(int row,int cnt){   //在row行进行试探，之前已经放了cnt个房子
    	if(row==n){
    		ans=max(ans,cnt);
    		return ;
    	}
    	for(int i=0;i<n;i++){
    		if(mp[row][i]=='X'){
    			vx[row]=0;
    			vy[i]=0;
    		}else{
    			if(!vx[row]&&!vy[i]){
    				vx[row]=1;
    				vy[i]=1;
    				dfs(row,cnt+1);  //继续在这行试探能不能放房子
    				dfs(row+1,cnt+1);  //直接去下一行试探能不能放房子
    				vx[row]=0;
    				vy[i]=0;
    			}
    		}
    		
    	}
    	dfs(row+1,cnt);  //不放房子，去下一行进行试探
    }
    
    int main(){
    	while(~scanf("%d",&n)){
    		if(n==0) break;
    		for(int i=0;i<n;i++){
    			scanf("%s",mp[i]);
    		}
    		ans=-1;
    	  /*memset(vx,0,sizeof(vx));
    		memset(vy,0,sizeof(vy));*/
    		dfs(0,0);
    		printf("%d\n",ans);
    	}
    	return 0;
    }

[ZOJ1002 Fire Net]: https://cn.vjudge.net/contest/273076#problem/A