zoj1002

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

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

两个及以上blockhouse不能位于同一行或者同一列
如果有wall，两个blockhouse可以位于其两侧
blockhouse只能建在空地
注意的点

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

include

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;
}