ACM 639 Don’t Get Rooked
作法:DFS
想法:一直去搜尋可以擺放的位子
/********************************************************/
#include<stdio.h>
#include<stdlib.h>
int map[5][5]={0},max;
int n;
int check(int a,int b)
{
int a1,find=0;
for(a1=a;a1<n;a1++)
{
if(map[a1][b]==1) {find=1;break;}
if(map[a1][b]==-1) break;
}
for(a1=a;a1>=0;a1--)
{
if(map[a1][b]==1) {find=1;break;}
if(map[a1][b]==-1) break;
}
for(a1=a;a1<n;a1++)
{
if(map[a][a1]==1) {find=1;break;}
if(map[a][a1]==-1) break;
}
for(a1=a;a1>=0;a1--)
{
if(map[a][a1]==1) {find=1;break;}
if(map[a][a1]==-1) break;
}
if(find==0) return 0;
else return 1;
}
void DFS(int many)
{
if(max<many) max=many;
int a,b;
for(a=0;a<n;a++)
for(b=0;b<n;b++)
if(check(a,b)==0&&map[a][b]==0)
{
map[a][b]=1;
DFS(many+1);
map[a][b]=0;
}
}
main()
{
char x[6]={0};
while(scanf("%d",&n)==1&&n!=0)
{
int a,b;
for(a=0;a<5;a++)
for(b=0;b<5;b++) map[a][b]=0;
for(a=0;a<n;a++)
{
scanf("%s",x);
for(b=0;b<n;b++)
if(x[b]=='X') map[a][b]=-1;/*-1代表牆壁*/
}
max=0;
DFS(0);
printf("%d\n",max);
}
return 0;
}