POJ 2488 A Knight's Journey(DFS、记录路径)
程序员文章站
2024-02-11 17:18:52
...
题目链接:点击这里
The knight can start and end on any square of the board. 被这句吓到了,弄了 次BFS,搞了一个小时也没搞出来。
参考链接:https://blog.csdn.net/lyhvoyage/article/details/18355471
大致题意:给出一个 行 列的国际棋盘,马可以从任意一个格子开始走,问马能否不重复的走完所有的棋盘。如果可以,输出按字典序排列最小的路径。打印路径时,列用大写字母表示( 表示第一列),行用阿拉伯数字表示(从 开始),先输出列,再输出行。
分析:如果马可以不重复的走完所有的棋盘,那么它一定可以走到 这个格子。所以我们只需从 这个格子开始搜索,就能保证字典序是小的;除了这个条件,我们还要控制好马每次移动的方向,控制方向时保证字典序最小(即按照下图中格子的序号搜索)。控制好这两个条件,直接从A1开始深搜就行了。
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<stack>
#include<queue>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
const int MOD = 10000007;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
const int X[8] = {-1, 1, -2, 2, -2, 2, -1, 1};
const int Y[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
int row, col, path[30][2];
bool vis[30][30], flag;
void DFS(int x, int y, int idx)
{
path[idx][0] = x;
path[idx][1] = y;
if(idx==row*col)
{
flag = true;
return;
}
for(int i = 0; i < 8; i++)
{
int newx = x + X[i];
int newy = y + Y[i];
if(newx>=1&&newx<=row&&newy>=1&&newy<=col&&!vis[newx][newy]&&!flag)
{
vis[newx][newy] = true;
DFS(newx, newy, idx+1);
vis[newx][newy] = false;
}
}
}
int main()
{
int t;
scanf("%d", &t);
for(int k = 1; k <= t; k++)
{
scanf("%d%d", &row, &col);
flag = false;
for(int i = 1; i <= row; i++)
for(int j = 1; j <= col; j++)
vis[i][j] = false;
printf("Scenario #%d:\n", k);
vis[1][1] = true;
DFS(1,1,1);
if(flag)
{
for(int i = 1; i <= row*col; i++)
printf("%c%d", 'A'+path[i][1]-1, path[i][0]);
printf("\n");
}
else
printf("impossible\n");
if(k<t) printf("\n");
}
return 0;
}
推荐阅读
-
POJ 2488 A Knight's Journey(DFS、记录路径)
-
POJ 2488 A Knight's Journey (DFS深搜)
-
POJ-2488,A Knight's Journey(DFS)
-
[POJ2488]A Knight's Journey(DFS)
-
poj-2488 A Knight's Journey
-
POJ-2488 A Knight's Journey
-
poj-2488 a knight's journey(搜索题)
-
poj-2488 a knight's journey(搜索题)
-
A - A Knight's Journey (poj2488)(dfs经典)