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;
}
补充：软件开发 , C++ ,
