|
|
http://poj.org/problem?id=2488dfs：我暈，這個是需要按照字典序來遍歷搜索和輸出的?。?！字典序啊字典序?。。?！代碼很難看，將就將就吧，有時間再改改：  
#include<stdio.h>
#include<string.h>
#include<math.h>
int xt,yt,count,steps;
int vis[27][27],step[700][2];
int go[8][2]={{-1,-2},{1,-2},{-2,-1},{2,-1},{-2,1},{2,1},{-1,2},{1,2}};
int dfs(int x,int y)
{
int i,x1,y1;
count++;
if (count==xt*yt)
{
steps++;
step[steps][0]=x;
step[steps][1]=y;
return 1;
}
for (i=0;i<8 ;i++ )
{
x1=x+go[i][0];
y1=y+go[i][1];
if (x1>=1&&x1<=xt&&y1>=1&&y1<=yt&&!vis[x1][y1])
{
vis[x1][y1]=1;
if (dfs(x1,y1))
{
steps++;
step[steps][0]=x;
step[steps][1]=y;
return 1;
}
vis[x1][y1]=0;
}
}
count--;
return 0;
}
int main()
{
int t,i,tot,flag;
scanf("%d",&tot);
for (t=1;t<=tot ;t++ )
{
scanf("%d%d",&xt,&yt);
printf("Scenario #%d:\n",t);
memset(vis,0,sizeof(vis));
vis[1][1]=1;
count=0;
steps=0;
flag=dfs(1,1);
if (!flag)
printf("impossible\n");
else
{
for (i=steps;i>=1 ;i-- )
printf("%c%d",64+step[i][1],step[i][0]);
printf("\n");
}
if (t<tot)
printf("\n");
}
return 0;
}
改了好久好久啊，要慢慢注意這個問題咯！！
|