2488A Knight's Journey

超奇葩的题目。。。。早上错了，下午没有怎么改就通过了.....

我的代码

#include "iostream"
#include "string.h"
using namespace std;
int map[26][26];
int num[8][2]={{-1,-2},{1,-2},{-2,-1},{2,-1},{-2,1},{2,1},{-1,2},{1,2}};
int top=0,p,q;
struct{
  int x,y;
}ans[26];

bool check(){
  int i,j;
  for(i=1;i<=p;i++){
    for(j=1;j<=q;j++){
      if(map[i][j]==0)return 0;
    }
  }
  return 1;
}

bool dfs(int a,int b){
  int flag=0,i;
  map[a][b]=1;
  for(i=0;i<=7;i++){
    int temx=a+num[i][0];
    int temy=b+num[i][1];
    if(temx>=1&&temx<=p&&temy>=1&&temy<=q&&map[temx][temy]==0){
      flag=1;
      ans[top].x=temx;ans[top].y=temy;top++;
      if(dfs(temx,temy))return 1;
    }
  }
  if(!flag){
    if(check())return 1;
  }
  map[a][b]=0;top--;
  return 0;
}

int main(){
  int ncase,x,y,i,j,flag,temp,step=1;
  cin>>ncase;
  while(ncase--){
    cin>>p>>q;
    top=0;
    memset(map,0,sizeof(map));
    ans[top].x=1;ans[top].y=1;top++;
    cout<<"Scenario #"<<step++<<":"<<endl;
    if(dfs(1,1)){
      for(i=0;i<top;i++){
      cout<<(char)(ans[i].y-1+'A')<<ans[i].x;
      }
      cout<<endl;
    }
    else cout<<"impossible"<<endl;
    cout<<endl;
  }
}

我是用了递归方式，看看人家用循环的方法

#include <iostream>
using namespace std;
int main()
{
    int i,k,n,p,q,s,t,ci,cj,queue[27],ti,tj;
    bool chess[26][26];
    const int dir[8][2]={{-1,-2},{1,-2},{-2,-1},{2,-1},{-2,1},{2,1},{-1,2},{1,2}};
    char a,b;
    scanf("%d",&n);
    for(k=1;k<=n;k++)
    {
        scanf("%d %d", &p, &q);
        memset(chess,0,sizeof(chess));
        ci=cj=t=queue[0]=0;chess[0][0]=true;s=1;
        while (s<p*q&&s>0)
        {
            for(i=t;i<8;i++)
            {
                ti=ci+dir[i][0];tj=cj+dir[i][1];
                if (ti>=0&&ti<p&&tj>=0&&tj<q&&!chess[ti][tj])
                {
                    ci=ti;cj=tj;
                    chess[ci][cj]=true;
                    queue[s]=i;t=0;s++;
                    break;
                }
            }
            if(i==8){
                s--;t=queue[s]+1;
                chess[ci][cj]=false;
                ci-=dir[queue[s]][0],cj-=dir[queue[s]][1];
            }
        }
        printf("Scenario #%d:
", k);
        if (s==p*q)
        {
            a='A',b='1';printf("%c%c", a, b);
            for(i=1;i<p*q;i++)
            {
                b+=dir[queue[i]][0],a+=dir[queue[i]][1];
                printf("%c%c", a, b);
            }
            printf("

");
        }
        else printf("impossible

");
    }
    return 0;
}

不错！！！！