1152. 简单的马周游问题Constraints
Time Limit: 1 secs, Memory Limit: 32 MB , Special Judge
Description
在一个5 * 6
为了便于表示一个棋盘，我们按照从上到下，从左到右对棋盘的方格编号，如下所示：
123456
789101112
131415161718
192021222324
252627282930
InputOutputSample Input4-1Sample Output注意：如果起点和输入给定的不同，重复多次经过同一方格或者有的方格没有被经过，都会被认为是错误的。Problem Source
ZSUACM Team Member
跟1153差不多，数据规模小了，可以去看看我的那篇，这里不做多陈述了：
很久之前做的：0.4s，没有优化的DFS：
#include <stdio.h>#include <string.h>int h[6][7], st[31], now, go[] = {-2, -1, -2, 1, -1, 2, 1, 2, 2, 1, 2, -1, 1, -2, -1, -2};void horse(int i, int j, int now) {int goi, goj;h[i][j] = 1;st[now] = i * 6 + j + 1;if (now == 29)return;for (int k = 0; k < 16; k += 2) {goi = i + go[k];goj = j + go[k + 1];if (goi >= 0 && goi <= 4 && goj >= 0 && goj <= 5 && h[goi][goj] == 0)horse(goi, goj, now + 1);}if (st[now + 1] == 0) {st[now] = 0;h[i][j] = 0;}return;}int main() {int n, i, j;while (scanf("%d", &n), n != -1) {now = 0;memset(h, 0, sizeof(h));memset(st, 0, sizeof(st));i = (n – 1) / 6;j = (n – 1) % 6;horse(i, j, now);printf("%d", st[0]);for (i = 1; i < 30; i++)printf(" %d", st[i]);printf("\n");}return 0;}然后做了1153之后回头重做此题：0s：
#include <stdio.h>#include <algorithm>#include <string.h>#include <vector>using namespace std;bool is_ok;int mapp[5][6];bool vis[5][6];int ans[30];int dir[8][2] = {-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2,-2,-1};void make_map() {for (int i = 0; i < 5; i++) {for (int j = 0; j < 6; j++) {mapp[i][j] = i * 6 + j + 1;}}}bool is_valid(int i, int j) {if (i < 0 || j < 0 || i > 4 || j > 5 || vis[i][j]) {return false;}return true;}int cal_roads(int ii, int jj) {//计算下一步有多少条路可以走int counter = 0;for (int i = 0; i < 8; i++) {int next_i = ii + dir[i][0];int next_j = jj + dir[i][1];if (is_valid(next_i, next_j)) {counter++;}}return counter;}struct choose {int ii;int jj;int roads;choose() {}choose(int i, int j) {ii = i;jj = j;roads = cal_roads(i, j);}};bool cmp(choose a, choose b) {return a.roads < b.roads;}void DFS(int from_i, int from_j, int num) {vector<choose> cho;for (int i = 0; i < 8; i++) {int next_i = from_i + dir[i][0];int next_j = from_j + dir[i][1];if (is_valid(next_i, next_j)) {cho.push_back(choose(next_i, next_j));}}if (cho.empty())//这里千万注意，我忘记了没有路的时候是要返回的，弄了一个下午。。return;sort(cho.begin(), cho.end(), cmp);if (num == 29) {ans[num] = mapp[cho[0].ii][cho[0].jj];is_ok = true;return;}for (int i = 0; i < (int)cho.size(); i++) {vis[cho[i].ii][cho[i].jj] = true;DFS(cho[i].ii, cho[i].jj, num + 1);if (is_ok) {ans[num] = mapp[cho[i].ii][cho[i].jj];return;} else {vis[cho[i].ii][cho[i].jj] = false;}}}int main() {int sp;make_map();while (scanf("%d", &sp) && sp != -1) {memset(vis, false, sizeof(vis));vis[(sp – 1) / 6][(sp – 1) % 6] = true;memset(ans, 0, sizeof(ans));ans[0] = sp;is_ok = false;DFS((sp – 1) / 6, (sp – 1) % 6, 1);for (int i = 0; i < 30; i++) {if (i != 0)printf(" ");printf("%d", ans[i]);}printf("\n");}return 0;}之后发现一个很好玩的现象，，其实我自己编了个程序来找，结果找到了成环的路：
如果你曾歌颂黎明，那么也请你拥抱黑夜
