Rescue

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

#define INF 0x3f3f3f3f

const int N = 210;

int dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0};

char g[N][N];
bool st[N][N];
int n, m;
int fx, fy;
int ans;

void dfs(int x, int y, int s) {
    if (s >= ans)
        return;

    if (g[x][y] == 'r') {
        if (s < ans)
            ans = s;
        return;
    }

    if (g[x][y] == 'x')
        s ++ ;

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

        int nx = x + dx[i], ny = y + dy[i];

        if (nx >= 0 && nx < n && ny >= 0 && ny < m && !st[nx][ny] && g[nx][ny] != '#') {
            st[nx][ny] = true;
            dfs(nx, ny, s + 1);
            st[nx][ny] = false;
        }
    }
}

int main() {
    while (cin >> n >> m) {
        ans = INF;
        memset(st, false, sizeof st);

        for (int i = 0; i < n; i ++ )

            for (int j = 0; j < m; j ++ ) {

                cin >> g[i][j];

                if (g[i][j] == 'a')
                    fx = i, fy = j;
            }

        dfs(fx, fy, 0);

        if (ans != INF)
            cout << ans << endl;
        else
            printf("Poor ANGEL has to stay in the prison all his life.\n");
    }

    return 0;
}

A计划

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 20;

int dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0};

char g[2][N][N];
bool st[2][N][N], flag;
int n, m, t;

struct node {
    int x, y, z;
    int s;
};

bool check(int a, int b, int c) {
    if (a < 0 || a  >= n || b < 0 || b >= m)
        return false;

    if (st[c][a][b])
        return false;

    if (g[c][a][b] == '*')
        return false;

    if (g[c][a][b] == '#' && g[!c][a][b] == '*')
        return false;

    if (g[c][a][b] == '#' && g[!c][a][b] == '#')
        return false;
    return true;
}

void bfs() {
    queue<node> q;
    node One, next;
    One.x = One.y = One.z = One.s = 0;
    q.push(One);
    st[0][0][0] = true;

    while (q.size()) {
        auto tou = q.front();
        q.pop();

        if (tou.s > t)
            return;

        if (g[tou.z][tou.x][tou.y] == 'P') {
            flag = true;
            return;
        }

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

            next.x = tou.x + dx[i], next.y = tou.y + dy[i];
            next.z = tou.z;

            if (check(next.x, next.y, next.z)) {
                st[next.z][next.x][next.y] = true;

                if (g[next.z][next.x][next.y] == '#')
                    next.z = !next.z;
                next.s = tou.s + 1;
                q.push(next);
            }
        }
    }
}

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

    while (T -- ) {
        cin >> n >> m >> t;

        memset(st, false, sizeof st);
        flag = false;

        for (int i = 0; i < 2; i ++ )

            for (int j = 0; j < n; j ++ )

                cin >> g[i][j];

        bfs();

        if (!flag)
            cout << "NO" << endl;
        else
            cout << "YES" << endl;
    }

    return 0;
}

A Knight’s Journey

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 30;

struct node {
    char str;
    int num;
} res[N * N];

bool st[N][N];
int cnt;
int p, q;

int dx[] = {-1, 1, -2, 2, -2, 2, -1, 1}, dy[] = {-2, -2, -1, -1, 1, 1, 2, 2};

bool dfs(int x, int y) {
    if (x >= 0 && x < p && y >= 0 && y < q && !st[x][y]) {
        st[x][y] = true;
        res[cnt].str = 'A' + y;
        res[cnt].num = x + 1;
        cnt ++ ;
    } else
        return false;

    if (cnt == p * q)
        return true;

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

        int nx = x + dx[i], ny = y + dy[i];

        if (dfs(nx, ny))
            return true;
    }

    st[x][y] = false;
    cnt -- ;
    return false;
}

int main() {
    int n, casei = 0;
    cin >> n;

    while (n -- ) {
        cin >> p >> q;

        memset(st, false, sizeof st);
        cnt = 0;

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

        if (dfs(0, 0)) {
            for (int i = 0; i < cnt; i ++ )

                cout << res[i].str << res[i].num;
            puts("");
        } else 
            cout << "impossible" << endl;

        puts("");
    }

    return 0;
}