首页 > 代码库 > Sicily Online Judge 1153.马的周游问题

Sicily Online Judge 1153.马的周游问题

2024-08-05 09:41:55   221人阅读

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.马的周游问题


联系
我们