提交了30次才AC －－－【附】POJ 2488解题报告

NND,这道题目，竟然提交了30次，搞的我晕过去了都！花费了将近12个小时！！
感一下，叹一声！如今的ACM，不仅锻炼编程，还锻炼了心理承受能力！！

1、注意格式，后面有一个空行
2、注意输出的时候的字典序－－什么叫字典序，要弄清楚
3、注意国际象棋的棋盘－－横的是字母，竖的是数字－－一定要按照这个格式，否则即使是答案对，也WA

有26次，全部栽在第3点上
3次栽在第二点上
1次栽在第一点上
PS:因为是字典序，所以，可以肯定只需要从（1，1）开始即可。不需要注意那句话：start at any position of the chessboard.

Source Code

Problem: 2488		User: omycle
Memory: 192K		Time: 360MS
Language: C++		Result: Accepted

• Source Code
  

  #include <iostream>
  #include <string>
  using namespace std;
  bool ok=false;
  int col=0;
  int row=0;
  int zoufa[8][2]={{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};//
  int flag[50][50];//第0行的，第零列的全不要 
  typedef struct
  {
  int x;
  int y;
  }Step;
  Step  step[100];//记录路径呀 
  Step step_c[100];
  int Count=0;
  void print(int n);
  //数组比较函数
  bool cmpint()
  {
  int i=0;
  while(i<col*row)
  {
  if(step_c[i].x<step[i].x)
  return false;//不用
  if(step_c[i].y<step[i].y)
  return false;
  if(step_c[i].x>step[i].x)
  return true;//用
  if(step_c[i].y>step[i].y)
  return true;//用
    i++;
  }
  return false;
  }
  //终点处理函数
  void Output()
  {
  if(!ok) //第一次是赋值
  {
  int i=0;
  while(i<col*row)
  {
     step_c[i].x=step[i].x;
     step_c[i].y=step[i].y;
     i++;
  }
  }
  else //下面是进行比较：
  {
  if(cmpint())//如果小于，那么就复制数组
  {
  int i=0;
  while(i<col*row)
  {
      step_c[i].x=step[i].x;
      step_c[i].y=step[i].y;
      i++;
  }
  }//end if 复制完毕  
  }
  }
  //打印函数－－没有问题
  void print(int n)
  {
  printf("Scenario #%d:\n",n);
  if(ok)
  {
  int i=0;
  while(i<col*row)
  {
  //char a=step_c[i].y;
  printf("%c%d",step_c[i].x+64,step_c[i].y);//输出的时候应该y在前，x在后 
     i++;
  }
  printf("\n");
  printf("\n");
  }
  else
  {
  printf("impossible\n");
  printf("\n");
  }
  }
  void Digui(int y,int x)
  {
  if(Count==(col*row))
  {
  Output();//将路径去进行比较
    ok=true;
  // return ;
  }
  for(int i=0;i<8;i++)
  {
  if((x+zoufa[i][0]<=col)&&((x+zoufa[i][0])>=1)&&((y+zoufa[i][1])>=1)&&((y+zoufa[i][1])<=row)&&(!flag[y+zoufa[i][1]][x+zoufa[i][0]]))
  {
     flag[y+zoufa[i][1]][x+zoufa[i][0]]=true;//已经走过
  //记忆路径 
     step[Count].x=x+zoufa[i][0];
     step[Count].y=y+zoufa[i][1];
  //记忆路数 
     Count++;
  Digui(y+zoufa[i][1],x+zoufa[i][0]);
     Count--;
     step[Count].x=0;
     step[Count].y=0;
     flag[y+zoufa[i][1]][x+zoufa[i][0]]=false;
  }
  }
  }
  int main()
  {
  int n;
  scanf("%d",&n);
  int i=1;
  while(i<=n)
  {
    ok=false;
    Count=0;
  for(int k=0;k<50;k++)
  {
  for(int kk=0;kk<50;kk++)
      flag[k][kk]=false;
  }
  for(int j=0;j<100;j++)
  {
     step[j].x=0;
     step[j].y=0;
     step_c[j].x=0;
     step_c[j].y=0;
  }
  scanf("%d%d",&row,&col);
    step[Count].x=1;
    step[Count].y=1;
    flag[1][1]=true;
    Count++;
  Digui(1,1);
  print(i++);
  }
  return 0;
  }

  
  

优化：16ms 196K代码！

#include <iostream>
#include <string>
using namespace std;
bool ok=false;
int col=0;
int row=0;
int zoufa[8][2]={{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};//
int flag[50][50];//第0行的，第零列的全不要
typedef struct
{
int x;
int y;
}Step;
Step step[100];//记录路径呀

int Count=0;

void print(int n);

void print(int n)
{
printf("Scenario #%d:\n",n);
if(ok)
{
   int i=0;
   while(i<col*row)
   {
    printf("%c%d",step[i].x+64,step[i].y);//输出的时候应该y在前，x在后
    i++;
   }
   printf("\n");
   printf("\n");
}
else
{
   printf("impossible\n");
   printf("\n");
}

}
void Digui(int y,int x)
{
if(Count==(col*row))
{  
   ok=true;
}
if(!ok)
{
   for(int i=0;i<8&&!ok;i++)
   {
    if((x+zoufa[i][0]<=col)&&((x+zoufa[i][0])>=1)&&((y+zoufa[i][1])>=1)&&((y+zoufa[i][1])<=row)&&(!flag[y+zoufa[i][1]][x+zoufa[i][0]]))
    {
     flag[y+zoufa[i][1]][x+zoufa[i][0]]=true;//已经走过
     //记忆路径
     step[Count].x=x+zoufa[i][0];
     step[Count].y=y+zoufa[i][1];
     //记忆路数
     Count++;
     Digui(y+zoufa[i][1],x+zoufa[i][0]);
     Count--;
     //step[Count].x=0;
     //step[Count].y=0;
     flag[y+zoufa[i][1]][x+zoufa[i][0]]=false;
    }
   }
}

}
int main()
{
int n;
scanf("%d",&n);
int i=1;
while(i<=n)
{
   ok=false;
   Count=0;  
   for(int k=0;k<50;k++)
   {
    for(int kk=0;kk<50;kk++)
     flag[k][kk]=false;
   }
   for(int j=0;j<100;j++)
   {
    step[j].x=0;
    step[j].y=0;
   }
   scanf("%d%d",&row,&col);
   step[Count].x=1;
   step[Count].y=1;
   flag[1][1]=true;
   Count++;
   Digui(1,1);
   print(i++);
}
return 0;
}