首页 > 代码库 > 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)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。