uva639(放車問題）-回溯法

[cpp]   #include<stdio.h>   char s[8];   int map[5][5],n;   int ok(int a,int b)   {       for(int i=a;i>=0;i--)           if(map[i][b]<0) return 0;           else if(map[i][b]==0) break;           for(int j=b;j>=0;j--)               if(map[a][j]<0) return 0;               else if(map[a][j]==0) break;               return 1;   }   int dfs(int i,int j)   {       int max=0,count=0;       while(i<n)       {           if(map[i][j]&&ok(i,j))           {               map[i][j]=-1;               count=dfs(i,j+1)+1;               if(max<count) max=count;               map[i][j]=1;           }           if(j>=n-1)           {               i++;               j=0;           }           else j++;       }       return max;   }   int main()   {       int i,j;       while(scanf("%d",&n)==1&&n)       {           for(i=0;i<n;i++)           {               scanf("%s",s);               for(j=0;j<n;j++)                   if(s[j]=='.') map[i][j]=1;                   else if(s[j]=='X') map[i][j]=0;           }           printf("%d\n",dfs(0,0));       }       return 0;   }