POJ 2488 A Knight's Journey

题意：给一个p*q的棋盘，问你能不能遍历整个棋盘的每一个方格，如果能输出路径，不能则impossible.  简单的深度遍历，得看看0msAC的有什么不同，这个是32ms,在输出时注意先输出列再输出行，例用大写字母表示结果按字典序排序，所有在遍历的时候先要从列小的开始。

代码：

[cpp]
#include<iostream> 
using namespace std; 
int d[8][2]={{-1,-2},{1,-2},{-2,-1},{2,-1},{-2,1},{2,1},{-1,2},{1,2}}; 
bool visit[30][30],success; 
int n,m,k,path[30][2]; 
bool Judge(int i,int j) 
{ 
     if(i>=0&&j>=0&&i<n&&j<m) return true; 
     return false; 
} 
bool Mark() 
{ 
     for(int i=0; i<n; i++) 
      for(int j=0; j<m; j++) 
          if( !visit[i][j]) 
            return false;   
      return true; 
} 
void Search(int x,int y) 
{ 
     int i,px,py,flag; 
     visit[x][y]=true; 
    // printf("%d %d\n",x,y); 
     for( i=0,flag=0; i<8&&!success; i++){ 
          px=x+d[i][0]; 
          py=y+d[i][1]; 
          if( Judge(px,py)&&!visit[px][py]){ 
              flag=1; 
              Search(px,py); 
          } 
     } 
     if( !flag&&Mark()){ 
      //  printf("%d  %d\n",x,y); 
         success=true; 
     } 
     if( !success) 
         visit[x][y]=false; 
     else{ 
          path[k][0]=x; 
          path[k][1]=y; 
          k++; 
     } 
} 
int main() 
{ 
    int t,i,j; 
    scanf("%d",&t); 
    for(int ca=1; ca<=t; ca++){ 
            success=false; 
            scanf("%d%d",&n,&m); 
            printf("Scenario #%d:\n",ca); 
            memset(path,0,sizeof(path)); 
            memset(visit,false,sizeof(visit)); 
            k=0; 
            if( n==1&&m!=1||m==1&&n!=1) 
                printf("impossible"); 
            else{ 
                 for( i=0; i<m&&!success; i++){ 
                      for( j=0; j<n; j++){ 
                           Search(j,i); 
                           if( success) 
                               break; 
                      } 
                 } 
                 if( !success) 
                     printf("impossible"); 
                 else{ 
                      for( i=k-1; i>=0; i--) 
                           printf("%c%d",'A'+path[i][1],path[i][0]+1); 
                 } 
            } 
            printf("\n\n"); 
    } 
} 

补充：软件开发 , C++ ,

上一个：lightoj 1231 DP 背包计数
下一个：Zoj 3537 Cake (DP_最优三角形剖分)