【POJ2488】A Knight's Journey

本题知识点：深度优先搜索 + 回溯 + 剪枝 + 字典序

题意是给你一个由 p，q 组成一个矩形的棋盘，让你用马棋在这上面走，是否能一线走完这 p * q 个格子。

关于这条路线是怎么走的，自己动手在纸上模拟一下样例3棋子行走的过程就可以了。

所以这种一线走完的题意可以很清楚地想到是深搜。

我第一次写的时候是没有回溯的，没有回溯的话，就会走回路，提交了一遍WA了，所以这里是不能走回路的，必须要用回溯。

如果都能走到的话，那所走的步数肯定是 p * q，所以这里是判断是否已走完的一个判断。当已达成的话，所得到的路径肯定是答案的路径（至于为什么，我也说不出个好证明来tclquq），得到这个路径后，就要进行剪枝，即中断搜索。

题目输出要求是路径输出要按照字典序输出，所以深搜时的方向一定先要按照字典序方向去走（这里也请大家自己思考一下，怎样走才是最小的字典序）。_{因为这个字典序差点搞崩我心态，所以大家一定要耐心看清楚题目啊，当思路都没问题时，重新读下题目是很重要的。}另外，输出时候还要多一个换行符。

下面请看下代码吧

// POJ 2488

#include<iostream>

#include<cstdio>

#include<vector>

#include<string>

#include<cstring>

using namespace std;

bool take[10][10];

int T, H, W;

int ans_size, temp_size;

string ans[30], temp[30];

bool ok;

//vector<string> temp, ans;

// WA 的行走模式

//int rh[] = { 2, 2, 1, -1, -2, -2, -1, 1 };

//int rw[] = { -1, 1, 2, 2, 1, -1, -2, -2 };

// AC 的行走模式

int rh[] = { -1, 1, -2, 2, -2, 2, -1, 1 };

int rw[] = { -2, -2, -1, -1, 1, 1, 2, 2 };

void dfs(int h, int w){

    take[h][w] = true;

    if(temp_size == H * W){

        ok = true;

        ans_size = 0;

        for(int i = 0; i < temp_size; i++){

//            ans.push_back(temp[i]);

            ans[ans_size++] = temp[i];

        }

        return ;

    }

    for(int i = 0; i < 8; i++){

        int nh = h + rh[i], nw = w + rw[i];

        if(1 <= nh && nh <= H && 1 <= nw && nw <= W && !take[nh][nw]){

            string a = "";

            a += (char)(nw - 1 + 'A');

            a += (char)(nh + '0');

            temp[temp_size++] = a;

//            temp.push_back(a);

            dfs(nh, nw);

            temp_size--;   // 回溯

            if(ok) return ; // 剪枝

//            temp.pop_back();

        }

    }

    take[h][w] = false;

}

int main()

{

//    freopen("test.txt", "r", stdin);

    scanf("%d", &T);

    for(int k = 1; k <= T; k++) {

        ok = false;

        memset(take, false, sizeof(take));

//        ans.clear();

//        temp.clear();

        ans_size = temp_size = 0;

        scanf("%d %d", &H, &W);

        string a = "A1";

        temp[temp_size++] = a;

//        temp.push_back(a);

        dfs(1, 1);

        printf("Scenario #%d:\n", k);

        if(ans_size == H * W){

            for(int i = 0; i < ans_size; i++){

                cout << ans[i];

            } cout << endl;

        }

        else cout << "impossible\n";

        cout << endl;

    }

    return 0;

}

巴特西

【POJ2488】A Knight's Journey

最新文章

热门文章