zoj1002

小灰灰 2023-03-14 05:53 40阅读 0赞

[题目传送门][Link 1]  
题目大意：  
在一个最大为4\*4的方格内建blockhouse（  
碉堡）  
但是有条件

1.  两个及以上blockhouse不能位于同一行或者同一列
2.  如果有wall，两个blockhouse可以位于其两侧
3.  blockhouse只能建在空地  
    注意的点
4.  多次输入；输入0时，结束  
    解题思路：  
    方格最大是4\*4，那么我们就简单点，使用暴力的方法，枚举也行，深搜也行，其实两者差不多。最大枚举次数为216,即每个格子都有两种可能，放和不放。深搜的时候要记得回溯。枚举的话，就可以写16重循环，每重循环设放和不放。  
    优化：其实我们没必要进行16重循环，我们用一个状态数组记录点为“。”的坐标，再看看总坐标数为多少，就可以确定枚举的次数了。

#include<iostream>
    using namespace std;
    int n,ans,count;
    char s[5][5];
    struct node 
    { 
    	int x,y;
    } v[20];
    bool judge(int row,int col)//判断插入一个炮垒是否合法 
    { 
    	int i,j,flag1=1,flag2=1;
    	for(i=1;i<col;i++)//在行判断 
    	{ 
    		if(s[row][i]=='a')
    		flag1=0;
    		if(s[row][i]=='X')
    		flag1=1;
    	}
    	for(i=1;i<row;i++)//在列判断 
    	{ 
    		if(s[i][col]=='a')
    		flag2=0;
    		if(s[i][col]=='X')
    		flag2=1;
    	}
    	if(flag1&&flag2)
    	return true;
    	return false;
    }
    void dfs(int num,int cur)//状态数组当前编号，当前放置碉堡数 
    { 
    	int dx=v[num].x;
    	int dy=v[num].y;
    	if(num==count)
    	{ 
    		ans=max(ans,cur);
    		return ;
    	}
    	int i,j;
    	for(i=1;i<=2;i++)
    	{ 
    		if(i==1&&judge(dx,dy))//表示放置碉堡 
    		{ 
    		    s[dx][dy]='a';//a表示放置碉堡
    		    dfs(num+1,cur+1);
    		}
    		else if(i==2)//不放置碉堡 
    		{ 
    			s[dx][dy]='.';//回溯 
    			dfs(num+1,cur); 
    		}
    	}
    }
    int main()
    { 
    	int i,j;
    	while(cin>>n&&n)
    	{ 
    	count=0;//复位 
    	ans=0;//复位 
    	for(i=1;i<=n;i++)
    	for(j=1;j<=n;j++)
    	{ 
    		cin>>s[i][j];
    		if(s[i][j]=='.')
    		v[count++]={ i,j};	
    	}
    	dfs(0,0);
    	cout<<ans<<endl;
    	}
    }

[Link 1]: https://zoj.pintia.cn/problem-sets/91827364500/problems/91827364501