首页 > 代码库 > Sicily Online Judge 1153.马的周游问题
Sicily Online Judge 1153.马的周游问题
1153. 马的周游问题
Constraints
Time Limit: 1 secs, Memory Limit: 32 MB , Special Judge
Description
和题目C同样的任务,这里只是把棋盘扩大到标准的国际象棋。对这样一个8 * 8的棋盘用同样的方法编号如下:
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
Input
输入有若干行。每行一个整数N(1<=N<=64),表示马的起点。最后一行用-1表示结束,不用处理。
Output
对输入的每一个起点,求一条周游线路。对应地输出一行,有64个整数,从起点开始按顺序给出马每次经过的棋盘方格的编号。相邻的数字用一个空格分开。
Sample Input
4-1
Sample Output
注意:如果起点和输入给定的不同,重复多次经过同一方格或者有的方格没有被经过,都会被认为是错误的。
Problem Source
ZSUACM Team Member
解题思路:
使用深搜,以优先走可走情况最少的下一步为条件剪枝。
源码:
// Problem#: 1153// Submission#: 3188714// The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License// URI: http://creativecommons.org/licenses/by-nc-sa/3.0/// All Copyright reserved by Informatic Lab of Sun Yat-sen University#include <stdio.h>#define DIM 8/*int chessBoard[40] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30 }; */bool visited[9][9];int road[70];int op[8][2] = { { -2, -1 }, { -1, -2 }, { +1, -2 }, { +2, -1 }, { +2, +1 }, { +1, +2 }, { -1, +2 }, { -2, +1 },};int countNext(int curR, int curC) { int count = -1; for (int i = 0; i < 8; i++) { if (curC + op[i][0] >= 0 && curC + op[i][0] < DIM && curR + op[i][1] >= 0 && curR + op[i][1] < DIM && visited[curR + op[i][1]][curC + op[i][0]] == false) { count++; } } return count;}int selectNext(int curR, int curC) { int minCount = -1; int nextR = 0; int nextC = -1; for (int i = 0; i < 8; i++) { if (curC + op[i][0] >= 0 && curC + op[i][0] < DIM && curR + op[i][1] >= 0 && curR + op[i][1] < DIM && visited[curR + op[i][1]][curC + op[i][0]] == false) { int cNext = countNext(curR + op[i][1], curC + op[i][0]); if (minCount == -1 || minCount > cNext) { minCount = cNext; nextR = curR + op[i][1]; nextC = curC + op[i][0]; } } } return nextR * DIM + nextC + 1;}bool found;void trip(int curR, int curC, int count) { int next; int nextR; int nextC; if (count == 0) { visited[curR][curC] = true; count++; } else if (count == 64) { found = true; road[count] = curR * DIM + curC + 1; } while (1) { next = selectNext(curR, curC); if (next == 0) break; nextR = (next - 1) / DIM; nextC = (next - 1) % DIM; visited[nextR][nextC] = true; trip(nextR, nextC, count + 1); if (found == true) { road[count] = curR * DIM + curC + 1; return; } visited[nextR][nextC] = false; }}int main(int argc, char** argv) { int s; while (scanf("%d", &s) && s != -1) { found = false; for (int i = 0; i < DIM + 1; i++) for (int j = 0; j < DIM + 1; j++) visited[i][j] = false; trip((s - 1) / DIM, (s - 1) % DIM, 0); int check[65]; for (int i = 1; i < DIM * DIM; i++) { check[road[i]] = 99; printf("%d ", road[i]); } check[road[64]] = 99; printf("%d\n", road[DIM * DIM]); } return 0;}
Sicily Online Judge 1153.马的周游问题