POJ 2488 深搜dfs、

题意：模拟国际象棋中马的走棋方式，其实和中国象棋的马走的方式其实是一样的，马可以从给定的方格棋盘中任意点开始，问是否能遍历全部格子，能的话输出字典序最小的走棋方式，否则输出impossible

思路：只要能遍历全部的格子，就一定会走A1这个点，而且这个点的字典序是最小的，保证了这点的话还需要保证dfs的8个方向也要按照字典序最小来走，这样就可以确保所走的路径就是字典序最小的

坑爹：自己忘记输出Scenario #i，一连WA了几发，就是不知道自己错在哪里，顺便发一个对照的程序吧我的程序过16MS，他的程序0MS

先贴自己的

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 const int qq=;

 int vis[qq][qq];

 int dx[]={-,-,-,-,,,,},

     dy[]={-,,-,,-,,-,};

 int map[qq][qq];

 int n,m,flag,ans;

 int check(int y,int x)

 {

     if(x<||y<||x>m||y>n||map[y][x])

         return ;

     return ;

 }

 void dfs(int y,int x,int step)

 {

     if(flag)    return;

     if(check(y,x))    return;

     vis[step][]=x;

     vis[step][]=y;

     if(step==n*m){

         flag=;

         ans=step;

         return;

     }

     for(int i=;i<;++i){

         map[y][x]=;

         dfs(y+dy[i],x+dx[i],step+);

         map[y][x]=;

     }

     return;

 }

 int main()

 {

     int t,o=;scanf("%d",&t);

     while(t--)

     {

         flag=;

         scanf("%d%d",&n,&m);

         memset(vis,,sizeof(vis));

         memset(map,,sizeof(map));

         ans=;

         dfs(,,);

         printf("Scenario #%d:\n",o++);

         if(ans!=n*m){

             printf("impossible");

         }

         else{

             for(int i=;i<=ans;++i){

             printf("%c",vis[i][]+'A'-);

             printf("%d",vis[i][]);

             }

         }

         printf("\n");

         if(t!=)    printf("\n");

     }

     return ;

 }

 #include<cstdio>

 .#include<cstring>

 .#include<algorithm>

 .using namespace std;

 .

 .int path[][], vis[][], p, q, cnt;

 .bool flag;

 .

 .int dx[] = {-, , -, , -, , -, };

 .int dy[] = {-, -, -, -, , , , };

 .

 .bool judge(int x, int y)

 .{

 .    if(x >=  && x <= p && y >=  && y <= q && !vis[x][y] && !flag)

 .        return true;

 .    return false;

 .}

 .

 .void DFS(int r, int c, int step)

 .{

 .    path[step][] = r;

 .    path[step][] = c;

 .    if(step == p * q)

 .    {

 .        flag = true;

 .        return ;

 .    }

 .    for(int i = ; i < ; i++)

 .    {

 .        int nx = r + dx[i];

 .        int ny = c + dy[i];

 .        if(judge(nx,ny))

 .        {

 .

 .            vis[nx][ny] = ;

 .            DFS(nx,ny,step+);

 .            vis[nx][ny] = ;

 .        }

 .    }

 .}

 .

 .int main()

 .{

 .    int i, j, n, cas = ;

 .    scanf("%d",&n);

 .    while(n--)

 .    {

 .        flag = ;

 .        scanf("%d%d",&p,&q);

 .        memset(vis,,sizeof(vis));

 .        vis[][] = ;

 .        DFS(,,);

 .        printf("Scenario #%d:\n",++cas);

 .        if(flag)

 .        {

 .            for(i = ; i <= p * q; i++)

 .                printf("%c%d",path[i][] -  + 'A',path[i][]);

 .        }

 .        else

 .            printf("impossible");

 .        printf("\n");

 .        if(n != )

 .            printf("\n");

 .    }

 .    return ;

 .}

巴特西

POJ 2488 深搜dfs、

最新文章

热门文章