[POJ] 2488.A Knight's Journey

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

题目传送门
题意：日字走，一次走完给定的p*q棋盘，记录步骤，输出
思路：dfs + 回溯

#include <algorithm>
#include <bitset>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int p, q;
int dy[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
int dx[8] = {-1, 1, -2, 2, -2, 2, -1, 1};
int chess[26][26];
bool flag;
struct step {int x;char y;
} path[26];void dfs(int x, int y, int counts) {path[counts].x = x;path[counts].y = y + 'A' - 1;int x1, y1;if (counts == p * q) {flag = true;for (int i = 1; i <= p * q; i++) printf("%c%d", path[i].y, path[i].x);printf("\n");}if (flag) return;for (int i = 0; i < 8; i++) {x1 = x + dx[i];y1 = y + dy[i];if (x1 > 0 && x1 <= p && y1 > 0 && y1 <= q && !chess[x1][y1]) {chess[x1][y1] = 1;dfs(x1, y1, counts + 1);chess[x1][y1] = 0;}}
}int main() {int n;scanf("%d", &n);int c = 1;while (n--) {memset(chess, 0, sizeof(chess));flag = false;scanf("%d%d", &p, &q);printf("Scenario #%d:\n", c++);chess[1][1] = 1;dfs(1, 1, 1);if (!flag) printf("impossible\n");printf("\n");}system("pause");return 0;
}

这篇关于[POJ] 2488.A Knight's Journey的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---