POJ 2488 简单 DFS

本文主要是介绍POJ 2488 简单 DFS，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

经典的骑士游历问题。

有趣的是要输出字典序最小的一组解

更有趣的是

通过我题，我发现这种游历问题，一旦一个点可以遍历全部，那么所有点可以遍历全部，只要他有两种及以上的走的方式。

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>using namespace std;
#define MAX 1000009 
#define INF 0x3f3f3f3f
#define MS(x) memset(x,0,sizeof(x))
#define ll long long
#define P pair<int,int>
#define fst first
#define sec second
int n,m;
int dir[8][2]={-2,-1,-2,1,-1,-2,-1,2,1,-2,1,2,2,-1,2,1};
P path[100];
bool flag;
int used[20][20];
void dfs(int x,int y,int p)
{used[x][y]=1;path[p]=P(x,y);if(p==n*m-1||flag){flag=true;return ;}for(int i=0;i<8;i++){if(flag)return ;int tx=x+dir[i][0];int ty=y+dir[i][1];if(tx>=0&&tx<n&&ty>=0&&ty<m&&!used[tx][ty])dfs(tx,ty,p+1);}used[x][y]=0;return;
}int main()
{int cas;scanf("%d",&cas);for(int T=1;T<=cas;T++){flag=false;MS(used);scanf("%d%d",&m,&n);dfs(i,j,0);printf("Scenario #%d:\n",T);if(!flag)cout<<"impossible";else{for(int i=0;i<n*m;i++)printf("%c%d",path[i].fst+'A',path[i].sec+1);}cout<<endl<<endl;}return 0;
}

这篇关于POJ 2488 简单 DFS的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---