sicily 1152 简单马周游深度优先搜索及回溯算法

1152. 简单的马周游问题

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

Submit

#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 = 1;
    for (int i = 2; i <= 6; i++) {
        for (int j = 2; j <= 7; j++) {
            coors[value].x = i;
            coors[value].y = j;
            loc[i][j] = value++;
        }
    }
    
    int start;
    while (cin>>start&&start!=-1) {
          memset(visited, false, sizeof(visited));
          int steps = 0;
          stack<int> road;
          road.push(start);
          visited[road.top()] = true;
          search(road.top(), steps, road);
    }
    return 0;
}

// Problem#: 1152
// Submission#: 3021883
// 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 <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) {
               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 {
              //未达到上限的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 = 1;
    for (int i = 2; i <= 6; i++) {
        for (int j = 2; j <= 7; j++) {
            coors[value].x = i;
            coors[value].y = j;
            loc[i][j] = value++;
        }
    }
    
    int start;
    while (cin>>start&&start!=-1) {
          memset(visited, false, sizeof(visited));
          int steps = 0;
          stack<int> road;
          road.push(start);
          visited[road.top()] = true;
          search(road.top(), steps, road);
    }
    return 0;
}

sicily 1152 简单马周游 深度优先搜索及回溯算法