dfs

要注意的问题就是字典序。

 

其实就是从A1开始，

 

先搜索左边和上面的点。

 

注意要回溯

 

#include <iostream>
using namespace std;
int m,n;
int sum;
int count;
typedef struct tr
{
 int x;
 int y;
}TR;
TR fo[27][27];
void init()
{
 for(int i=0;i<=m;i++)
  for(int j=0;j&lt;=n;j++)
  {
   fo[i][j].x=-1;
   fo[i][j].y=-1;
  }
  sum=m*n;
  count=1;
  return ;
}
int dfs(int x,int y)
{
 if(count==sum)
  return 1;
 if(-1==fo[x-1][y-2].x&&-1==fo[x-1][y-2].y&&x-1>0&&y-2&gt;0)
 { 
  fo[x][y].x=x-1;
  fo[x][y].y=y-2;
  count++;
  if(dfs(x-1,y-2)) return 1;
  fo[x][y].x=-1;
  fo[x][y].y=-1;
  count--;
 }
 if(-1==fo[x+1][y-2].x&&-1==fo[x+1][y-2].y&&x+1<=m&&y-2>0)
 {
  fo[x][y].x=x+1;
  fo[x][y].y=y-2;
  count++;
  if(dfs(x+1,y-2)) return 1;
  fo[x][y].x=-1;
  fo[x][y].y=-1;
  count--;
 }
 if(-1==fo[x-2][y-1].x&&-1==fo[x-2][y-1].y&&x-2&gt;0&&y-1&gt;0)
 {
  fo[x][y].x=x-2;
  fo[x][y].y=y-1;
  count++;
  if(dfs(x-2,y-1)) return 1;
  fo[x][y].x=-1;
  fo[x][y].y=-1;
  count--;
 }
 if(-1==fo[x+2][y-1].x&&-1==fo[x+2][y-1].y&&x+2<=m&&y-1>0)
 {
  fo[x][y].x=x+2;
  fo[x][y].y=y-1;
  count++;
  if(dfs(x+2,y-1)) return 1;
  fo[x][y].x=-1;
  fo[x][y].y=-1;
  count--;
 }
 if(-1==fo[x-2][y+1].x&&-1==fo[x-2][y+1].y&&x-2&gt;0&&y+1<=n)
 {
  fo[x][y].x=x-2;
  fo[x][y].y=y+1;
  count++;
  if(dfs(x-2,y+1)) return 1;
  fo[x][y].x=-1;
  fo[x][y].y=-1;
  count--;
 }
 if(-1==fo[x+2][y+1].x&&-1==fo[x+2][y+1].y&&x+2&lt;=m&&y+1&lt;=n)
 {
  fo[x][y].x=x+2;
  fo[x][y].y=y+1;
  count++;
  if(dfs(x+2,y+1)) return 1;
  fo[x][y].x=-1;
  fo[x][y].y=-1;
  count--;
 }
 if(-1==fo[x-1][y+2].x&&-1==fo[x-1][y+2].y&&x-1>0&&y+2<=n)
 { 
  fo[x][y].x=x-1;
  fo[x][y].y=y+2;
  count++;
  if(dfs(x-1,y+2)) return 1;
  fo[x][y].x=-1;
  fo[x][y].y=-1;
  count--;
 }
 if(-1==fo[x+1][y+2].x&&-1==fo[x+1][y+2].y&&x+1&lt;=m&&y+2&lt;=n)
 {
  fo[x][y].x=x+1;
  fo[x][y].y=y+2;
  count++;
  if(dfs(x+1,y+2)) return 1;
  fo[x][y].x=-1;
  fo[x][y].y=-1;
  count--;
 }
 return 0;

}
void get_out()
{
 int i=1,j=1;
 cout&lt;&lt;"A1";
 while(fo[i][j].x!=-1&&fo[i][j].y!=-1)
 {
  cout&lt;&lt;char(fo[i][j].y+64)&lt;&lt;fo[i][j].x;
  int temp=i;
  i=fo[i][j].x;
  j=fo[temp][j].y;
 }
 cout&lt;&lt;endl;
 return ;
}
int main()
{   int t;
    cin >&gt;t;
 for(int i=1;i<=t;i++)
 {
  cin >&gt;m&gt;&gt;n;
  init();
  cout&lt;&lt;"Scenario #"&lt;&lt;i&lt;&lt;":"&lt;&lt;endl;
  if(!dfs(1,1))
  {
   cout&lt;&lt;"impossible"&lt;&lt;endl;
  }
  else
  get_out();
  cout&lt;&lt;endl;
 }
 return 0;

}