sicily 1152. 简单的马周游问题

summary

:

我本来是想找用来练习栈的题的，看到了这个题，一想，这个和八皇后问题有点类似， 可以用回溯解决，便开始了，纠结了2天，发现输不出答案来的，找了1天，终于找出了bug， 当看到黑色的屏幕上出现一行白色的一行数字时，我内牛满面............但是，ctrl+c,ctrl+v， 返回一了一个红红的WA，我检查了一下，发现第一人测试数据完了之后，栈没有清空， 还好C++允许在中间声明变量，我把stack对象放到中间，就解决问题了，然后还发现， 第一个测试数据完了之后，全都标志成了1了，我又把数组全部标志成了0，这时， 发现输入2时，没有输出的，我以为进入了循环，又在调试，调试了1天， 最后发现好像没什么问题，我就运行试试，可能是还没算出来，我就输入2， 在那里干等了10秒，发现出来了！心想，这个程序肯定超时了，交上去试试， 没想到返回了一个绿绿的AC，0.52sec，很明显，oj的测试用例不是2， 我纠结了3天的的1152，用栈来实现回溯的非递归做法，后来在网上查了一下， 有一个人用了回溯的递归实现，dsf(),百度了一下，原来是深度优先搜索，牛人！ 下面是我的代码，很长，效率很低，不过是我自己为了练习栈独立完成的。 要刷就刷这种题，水题一点也不好玩！

代码:

#include <iostream>
#include <stack>

using namespace std;

struct node{
    int v;
    int f;
}m[5][6];

typedef struct{
    int x,y,d,v;
}T;

int main()
{
    T e;
    int a[30];
    int n,i,j,k,g,h,b;
    int d[8][2] = { -2,-1, -1,-2, 1,-2, 2,-1, 
                    2,1, 1,2, -1,2, -2,1 };

    for(i = 0; i < 5; i++){
        for(j = 0; j < 6; j++){
            m[i][j].v = 6 * i + j + 1;
            m[i][j].f = 0;
        }
    }
    while(cin >> n && n != -1){
        stack<T> s;
        for(i = 0; i < 5; i++){
            for(j = 0; j < 6; j++){
                m[i][j].f = 0;
            }
        }
        e.x = i = n / 6;
        e.y = j = n % 6 - 1;
        e.v = m[i][j].v;
        m[i][j].f = 1;
        e.d = -1;
        k = e.d + 1;
        s.push(e);
        while(!s.empty()){
            i = s.top().x;
            j = s.top().y;
            k = s.top().d + 1;
            m[i][j].f = 0;
            s.pop();
            while(k < 8){
                g = i + d[k][0];
                h = j + d[k][1];
                if(g >= 0 && g <= 4 && h >= 0 && h <= 5 && !m[g][h].f){
                    e.x = i; 
                    e.y = j; 
                    e.d = k;
                    e.v = m[i][j].v;
                    m[i][j].f = 1;
                    s.push(e);
                    i = g;
                    j = h;
                    k = -1;
                }
                else if(s.size() == 29){
                    e.x = i;
                    e.y = j;
                    e.v = m[i][j].v;
                    s.push(e);
                    for(b = 0; !s.empty(); b++){
                        a[b] = s.top().v;
                        s.pop();
                    }
                    for(b--; b >= 1; b--){
                        cout << a[b] << " ";
                    }
                    cout << a[0] << endl;
                    k = 8;
                }
                k++;
            }
            if(k == 9)
                break;
        }
    }
    return 0;
}