2190: 【递归】冲突

2190: 【递归】冲突

时间限制: 1 Sec   内存限制: 64 MB

题目描述

监狱的每间牢房是一个不超过4×4的正方形，里面设有一些障碍，牢房里住着的犯人脾气都很大，只要两个犯人位于同一行或同一列即会发生冲突，但障碍物可以阻挡同行或同列犯人的冲突。问最多可放几个犯人而不会发生冲突。如下图所示，左边表示初始牢房样，右边4个显示了摆放方案，当然，最后两个方案是错误的。

输入

有多组测试数据，每组数据第一行为一个整数Ｎ表示牢房大小。随后Ｎ行描述牢房，其中X表示障碍。

所有测试数据结束的标志为０。

输出

输出最多可放的犯人数。

样例输入 Copy

4

.X..

....

XX..

....

2

XX

.X

3

.X.

X.X

.X.

3

...

.XX

.XX

4

....

....

....

....

0

样例输出 Copy

5

1

5

2

4

解析：搜索最基础的题。有疑问可以留言~~稍微有些繁琐，细心一些一定能做出来的！

#include<bits/stdc++.h>

using namespace std;

int a[10][10];

int maxx,n;

void dfs(int x,int y,int now){

maxx=max(maxx,now);

int xx,yy;

// if(n==2){

// cout<<x<<' '<<y<<' '<<now<<endl;

// }

if(x>n) return;

bool t;t=1;

for(int i=x;i<=n;i++){

if(a[i][y]==2) break;

if(a[i][y]==1) t=0;

}

// cout<<t;

for(int i=x;i>=1;i--){

if(a[i][y]==2) break;

if(a[i][y]==1) t=0;

}

// cout<<t;

for(int i=y;i<=n;i++){

if(a[x][i]==2) break;

if(a[x][i]==1) t=0;

}

// cout<<t;

for(int i=y;i>=1;i--){

if(a[x][i]==2) break;

if(a[x][i]==1) t=0;

}

// cout<<t;

yy=y+1;xx=x;

// cout<<t<<" "<<xx<<" "<<yy<<endl;

if(yy>n){yy=1;xx++;}

if(a[x][y]==2||!t) dfs(xx,yy,now);

else{

a[x][y]=1;dfs(xx,yy,now+1);

a[x][y]=0;dfs(xx,yy,now);

}

}

int main(){

// freopen("2190.in","r",stdin);

while(scanf("%d",&n)!=EOF){

if (n==0) break;

maxx=0;

char str[10];

memset(a,0,sizeof(a));

for(int i=0;i<n;i++){

cin>>str;

for(int j=0;j<n;j++)

if(str[j]=='.') a[i+1][j+1]=0;

else a[i+1][j+1]=2;

}

dfs(1,1,0);

cout<<maxx<<endl;

}

return 0;

}