Constraints

Time Limit: 1 secs, Memory Limit: 32 MB , Special Judge

Description

在一个5 * 6的棋盘中的某个位置有一只马，如果它走29步正好经过除起点外的其他位置各一次，这样一种走法则称马的周游路线，试设计一个算法，从给定的起点出发，找出它的一条周游路线。

为了便于表示一个棋盘，我们按照从上到下，从左到右对棋盘的方格编号，如下所示：

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

马的走法是“日”字形路线，例如当马在位置15的时候，它可以到达2、4、7、11、19、23、26和28。但是规定马是不能跳出棋盘外的，例如从位置1只能到达9和14。

Input

输入有若干行。每行一个整数N(1<=N<=30)，表示马的起点。最后一行用-1表示结束，不用处理。

Output

对输入的每一个起点，求一条周游线路。对应地输出一行，有30个整数，从起点开始按顺序给出马每次经过的棋盘方格的编号。相邻的数字用一个空格分开。

Sample Input

4-1

Sample Output

注意：如果起点和输入给定的不同，重复多次经过同一方格或者有的方格没有被经过，都会被认为是错误的。

Problem Source

ZSUACM Team Member

#include <iostream>#include <map>#include <stack>#include <vector>#include <cstring>using namespace std;typedef struct Coordinate {    int x;    int y;} Coor;bool visited[31];int loc[9][10]; //此在5*6格子数组中添加额外的行和列，拓展为9*10的数组，即设置边界，便于找到可以前进的节点 map<int, Coor> coors; //用于记录每个位置的坐标 //获得可以前进的节点，即符合“日”字形，且未访问过 vector<int> getAdjacents(int i, int j) {    vector<int> result;    if (loc[i-2][j-1] != 0 && visited[loc[i-2][j-1]] == false)       result.push_back(loc[i-2][j-1]);    if (loc[i-2][j+1] != 0 && visited[loc[i-2][j+1]] == false)       result.push_back(loc[i-2][j+1]);     if (loc[i-1][j-2] != 0 && visited[loc[i-1][j-2]] == false)       result.push_back(loc[i-1][j-2]);    if (loc[i-1][j+2] != 0 && visited[loc[i-1][j+2]] == false)       result.push_back(loc[i-1][j+2]);    if (loc[i+1][j-2] != 0 && visited[loc[i+1][j-2]] == false)       result.push_back(loc[i+1][j-2]);    if (loc[i+1][j+2] != 0 && visited[loc[i+1][j+2]] == false)       result.push_back(loc[i+1][j+2]);    if (loc[i+2][j-1] != 0 && visited[loc[i+2][j-1]] == false)       result.push_back(loc[i+2][j-1]);    if (loc[i+2][j+1] != 0 && visited[loc[i+2][j+1]] == false)       result.push_back(loc[i+2][j+1]);    return result;}void search(int start, int &steps, stack<int> &road) {     vector<int> adjacents = getAdjacents(coors[start].x, coors[start].y);     //当没有可以走的下一个格子时      if (adjacents.size() == 0) {        //如果已经走了29步，此时需要检测是否已经走完了所有节点         if (steps == 29) {           bool complete = true;           for (int j = 1; j <= 30; j++) {               if (visited[j] == false) {                  complete = false;                  break;               }           }           //是，则回溯输出依次经过的节点            if (complete == true) {               vector<int> result;               while(!road.empty()) {                   result.push_back(road.top());                   road.pop();               }               for (int j = result.size()-1; j >= 0; j--)                   cout << result[j] << " ";               cout << endl;           } else {              //否，则在保留已经经过了的节点的栈中删除该节点，同时使步数减一和设置该节点未访问过来使的可以              //通过其他节点到达该节点               visited[road.top()] = false;              steps--;              road.pop();           }        } else {              //未达到上限的29步，则直接保留已经经过了的节点的栈中删除该节点，同时使步数减一和设置该节点未访问过来使的可以              //通过其他节点到达该节点              visited[road.top()] = false;              steps--;              road.pop();        }     } else {          //当前节点存在相邻的可以走的节点，则依次深搜遍历相邻节点           for (int i = 0; i < adjacents.size(); i++) {              visited[adjacents[i]] = true;              steps++;              road.push(adjacents[i]);              search(road.top(), steps, road);          }          //刚开始这里未加 !road.empty()，出现runtime error的错误，因为在找到该路径之后，即上面          //的for循环跳出之后，此时road已经为空了，所以如果未判断!road.empty会是空的road调用           //此步是解决本题的关键，即当遍历完一个节点的所有相邻节点后，如果既没有达到遍历完所有节点，即!road.empty          //相邻节点也没有一个进栈的，即均不合格，则此时应该回溯，将该栈顶节点出栈，同时设置为未访问过，步数减一           if (!road.empty() && road.top() == start) {              visited[road.top()] = false;              steps--;              road.pop();          }     }}int main() {    memset(loc, 0, sizeof(loc));    int value = http://www.mamicode.com/1;>