当前位置：首页 > article >正文

acwing_3196_I‘m stuck

article 2025/1/13 7:28:54

acwing_3196_I’m stuck

//
// Created by HUAWEI on 2024/11/17.
//
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 50 + 5;
char g[N][N];// 地图
bool str1[N][N], str2[N][N]; // 判断1，判断2
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}; //上右下左
int R, C;

bool check(int x, int y, int k) {
    if (g[x][y] == '+' || g[x][y] == 'S' || g[x][y] == 'T')return true;
    if (g[x][y] == '-' && (k == 1 || k == 3))return true;
    if (g[x][y] == '|' && (k == 0 || k == 2))return true;
    if (g[x][y] == '.' && k == 2)return true;
    return false;
}

void dfs1(int x, int y) {
    str1[x][y] = true;
    for (int k = 0; k < 4; k++) {
        //玩家可以沿着四个方向走
        int a = x + dx[k];
        int b = y + dy[k];
        if (a < 0 || a >= R || b < 0 || b >= C || g[a][b] == '#')continue;
        if (str1[a][b])continue;
        if (check(x, y, k)) {
            dfs1(a, b);
        }
    }
}

void dfs2(int x, int y) {
    str2[x][y] = true;
    for (int k = 0; k < 4; k++) {
        //玩家可以沿着四个方向走
        int a = x + dx[k];
        int b = y + dy[k];
        if (a < 0 || a >= R || b < 0 || b >= C || g[a][b] == '#')continue;
        if (str2[a][b])continue;
        if (check(a, b, k ^ 2)) {
            // 注意这里和dfs1的区别 ！！！
            dfs2(a, b);
        }
    }
}

int main() {
    cin >> R >> C;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> g[i][j];
        }
    }
    int tx, ty;//存放终点的索引
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (g[i][j] == 'S') {
                //找到起点
                dfs1(i, j);
            } else if (g[i][j] == 'T') {
                //找到终点
                tx = i, ty = j;
                dfs2(i, j);
            }
        }
    }
    int res = 0;
    if (!str1[tx][ty])
        puts("I'm stuck!");
    else {
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (str1[i][j] && !str2[i][j]) {
                    res++;
                }
            }
        }
        cout << res << endl;
    }
    return 0;
}

注意事项：