摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法: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;     
}