c++ - 有没有办法到达最后的盒子 - GRAPH

Question

存在问题:第一个人“g”(第一个开始的人)必须到达最后一个盒子“e”，这样第二个人“l”(无论何时)都无法 catch 第一个人。男人可以左、右、上、下或留下。

例如:

Input:
6 7
RRRRRRR
R_e___R
R_____R
R_RRR_R
R_gRl_R
RRRRRRR

答案是"is"，因为有路(左、上、上、上、右)。

如何实现这个问题？

我正在使用 BFS 和 DFS。这是我的代码

#include <iostream>
#include <algorithm>
#include <stack>
#include <math.h>
#include <cstring>
#include <map>
#include <queue>
using namespace std;
const int MAX = 32;
char a[MAX][MAX];
int used[MAX][MAX], m1[MAX][MAX], m2[MAX][MAX];;

int movesx[8] = {-1, 1, 0, 0};
int movesy[8] = { 0, 0, -1, 1};

int n, m, c = 0, flag = 0;

struct pc {
    int x, y;
};

pc li, ga, fi;

queue <pc> q;
void BFS1(pc v) {

    pc from, to;
    memset(m1,0,sizeof(m1)); m1[v.y][v.x] = 0;
    memset(used, 0, sizeof(used));

    q.push(v); used[v.y][v.x] = 1;
    while(!q.empty())
    {
        from = q.front(); q.pop();

        for(int i = 0; i < 4; ++i) {
            int x = from.x + movesy[i], y = from.y + movesx[i];
            if( (a[y][x] == ' ' || a[y][x] == 'g' ) && !used[y][x]) {
                used[y][x] = 1;
                m1[y][x] = m1[from.y][from.x] + 1;
                pc temp;
                temp.x = x;
                temp.y = y;

                q.push(temp);
            }

        }
    }
}

void BFS2(pc v) {

    pc from, to;
    memset(m2,0,sizeof(m2)); m2[v.y][v.x] = 0;
    memset(used, 0, sizeof(used));

    q.push(v); used[v.y][v.x] = 1;
    while(!q.empty())
    {
        from = q.front(); q.pop();

        for(int i = 0; i < 4; ++i) {
            int y = from.y + movesy[i], x = from.x + movesx[i];
            if( (a[y][x] == ' ' || a[y][x] == 'l' ) && !used[y][x]) {
                used[y][x] = 1;
                m2[y][x] = m2[from.y][from.x] + 1;
                pc temp;
                temp.x = x;
                temp.y = y;

                q.push(temp);
            }

        }
    }
}

void DFS(pc v) {
    used[v.y][v.x] = 1;

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

        int x = v.x + movesx[i], y = v.y + movesy[i];

        if(a[y][x] == 'e') {
                c = 1;
                flag = 1;
                return;
        }

        if( (a[y][x] == ' ' ) && !used[y][x] && m2[y][x] < m1[y][x] && flag == 0 ) {
            pc temp;
            temp.x = x;
            temp.y = y;

            DFS(temp);
        }

    }
}

int main() {
        c = 0, flag = 0;
        memset(used, 0, sizeof(used));
        memset(a, 'R', sizeof(a));
        cin >> n >> m;
        string s;
        getline(cin, s);
        for(int i = 0; i < n; ++i) {
            getline(cin, s);
            for(int j = 0; j < m; ++j) {
                a[i][j] = s[j];
                if(a[i][j] == 'g') {
                    ga.x = j;
                    ga.y = i;
                }
                else if(a[i][j] == 'l') {
                    li.x = j;
                    li.y = i;
                }
                else continue;

            }
        }

        BFS1(li);
        BFS2(ga);

        memset(used, 0, sizeof(used));

        DFS(ga);
        if(c == 1) {
            cout << "YES" << endl;
        }
        else {
            cout << "NO" << endl;
        }

}

这是第二个代码:

#include <iostream>
#include <algorithm>
#include <stack>
#include <math.h>
#include <cstring>
#include <map>
#include <queue>
using namespace std;
const int MAX = 32;
char a[MAX][MAX];
int used[MAX][MAX], m1[MAX][MAX], m2[MAX][MAX];;

int an[1002][MAX][MAX];

int movesx[8] = {-1, 1, 0, 0, 0};
int movesy[8] = { 0, 0, -1, 1, 0};

int n, m, c = 0, flag = 0;

struct pc {
    int x, y;
};

pc li, ga;

void functionD() {

    for(int z = 1; z <= 1000; ++z) {
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < n; ++j) {

                if(an[z - 1][i][j] == 1) {
                    int x, y;
                    for(int k = 0; k < 5; ++k) {

                        x = j + movesx[k];
                        y = i + movesy[k];


                        if(x < m && y < n && x >= 0 && y >= 0) {

                            if(a[y][x] != 'R' && a[y][x] != 'e') {
                                an[z][y][x] = 1;
                            }

                        }

                    }

                }

            }
        }
    }


}

void DFS(pc v, int k) {
    used[v.y][v.x] = 1;

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

        int x = v.x + movesx[i], y = v.y + movesy[i];

        if(a[y][x] == 'e') {
                c = 1;
                flag = 1;
                return;
        }
        if(an[k][y][x] == 0 && a[y][x] != 'R' && !used[y][x] && flag == 0 && k <= 1000) {
            pc temp;
            temp.x = x;
            temp.y = y;
            DFS(temp, k + 1);
        }

    }
}

int main() {
    int nn; cin >> nn;

    for(int z = 0; z < nn; ++z) {
        c = 0, flag = 0;
        memset(used, 0, sizeof(used));
        memset(a, 'R', sizeof(a));
        cin >> n >> m;
        string s;
        getline(cin, s);
        for(int i = 0; i < n; ++i) {
            getline(cin, s);
            for(int j = 0; j < m; ++j) {
                a[i][j] = s[j];
                if(a[i][j] == 'g') {
                    ga.x = j;
                    ga.y = i;
                }
                else if(a[i][j] == 'l') {
                    li.x = j;
                    li.y = i;
                }

            }
        }
        an[0][li.y][li.x] = 1;

        functionD();



        DFS(ga, 1);


        if(c == 1) {
            cout << "YES" << endl;
        }
        else {
            cout << "NO" << endl;
        }

    }
}

编辑(作者 Jarod42):

我找到了一张失败的棘手 map :

9 9
RRRRRRRRR
R...Rg..R
R.RlRRR.R
R.R...R.R
R.RRR.R.R
R.Re....R
R.R.RRR.R
R.......R
RRRRRRRRR

l 无法保护对 e 的两种访问。

或者更简单

RRRRRRRRRR
R...RRRRRR
R.R...RRRR
RlReR...gR
R.R...RRRR
R...RRRRRR
RRRRRRRRRR

Answer 1

您必须首先创建从每次访问到 e 的 map 距离。

然后就是一个minmax(或者alpha-beta):

• 如果 g 当前位置在一个 map 距离小于 l 当前位置是相同的 map 距离，g 获胜。<
• 如果 l 在所有 map 距离中的距离小于或等于，则 g 输。
• else g 必须使用其有效 map 之一才能达到目标，l 用其 map (或支架)反击。

(注意:g 没有理由站着，因为 l 可能做同样的事情，我们处于同一点)。

(编辑:注意:在提供的链接中，似乎必须静态选择安全路径，因此动态部分(第 3 个项目符号)对于 g 来说是松散的)