首页 > 代码库 > poj A Knight's Journey(DFS)

poj A Knight's Journey(DFS)

题目链接:http://acm.hrbust.edu.cn/vj/index.php?c=problem-problem&id=190592

题意:给出p*q的棋盘,从(A,1)开始,走“日”字,问能否走完棋盘上所有的点,如果能,按字典序输出路径;

思路:DFS,并保存路径即可,注意处理走的方向顺序int dir[8][2]={{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};

#include <stdio.h>#include <string.h>int vis[30][30], ansx[30],ansy[30];int dir[8][2]={{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};int p,q,flag;void dfs(int x, int y, int num){    int i, j;    ansx[num]=x;    ansy[num]=y;    if(num==p*q)    {        flag=1;        return ;    }    for(i=0; i<8; i++)    {        int xx=x+dir[i][0];        int yy=y+dir[i][1];        if(xx<=q && xx>=1 && yy<=p && yy>=1 && !vis[xx][yy] && !flag)        {            //printf("%d %d\n",xx,yy);            //getchar();            vis[xx][yy]=1;            dfs(xx,yy,num+1);            vis[xx][yy]=0;        }    }}int main(){    int t,_case=1;    scanf("%d",&t);    while(t--)    {        if(_case!=1) printf("\n");        printf("Scenario #%d:\n",_case++);        scanf("%d%d",&p,&q);        memset(vis,0,sizeof(vis[0]));        vis[1][1]=1;        flag=0;        dfs(1,1,1);        if(flag)        for(int i=1; i<=p*q; i++)        {            printf("%c%d",ansx[i]+‘A‘-1,ansy[i]);        }        else printf("impossible");        printf("\n");    }    return 0;}

  

poj A Knight's Journey(DFS)