AOJ 1459 E-Circuit Is Now on Sale! (ICPC アジア 2024 E) (1Q)

これは比較的易しめだった。探索するだけ！

• 問題へのリンク

問題概要

下図のように「計算過程」を表す二次元グリッドが与えられる。文字 . 以外の文字は木をなしていて、葉には数値がかかれている。演算子 +、-、*、/ はそれぞれ「大きい方から小さい方に演算する」ことを表している。P が最終結果を表す。最終結果の値を求めよ。

6 8
3.......
#....P..
#....#.2
#.###*#+
##-....#
..1...4#

（この答えは (3 - 1) * (2 + 4) = 12）

制約

• 
• 計算過程は を超えない

考えたこと

文字 P から始めて、木 DP の要領で計算していけば OK。

コード

#include <bits/stdc++.h>
using namespace std;

vector<int> dx = {1, 0, -1, 0};
vector<int> dy = {0, 1, 0, -1};

int main() {
    int H, W;
    cin >> H >> W;
    vector<string> S(H);
    for (int i = 0; i < H; i++) cin >> S[i];

    int sx, sy;
    for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) {
        if (S[i][j] == 'P') sx = i, sy = j, S[i][j] = '#';
    }

    vector<vector<bool>> seen(H, vector<bool>(W, false));
    auto rec = [&](auto rec, int x, int y) -> long long {
        seen[x][y] = true;
        if (S[x][y] >= '0' && S[x][y] <= '9') return S[x][y] - '0';

        long long res;
        vector<long long> sub;
        for (int d = 0; d < 4; d++) {
            int x2 = x + dx[d], y2 = y + dy[d];
            if (x2 < 0 || x2 >= H || y2 < 0 || y2 >= W || seen[x2][y2]) continue;
            if (S[x2][y2] != '.') {
                sub.emplace_back(rec(rec, x2, y2));
            }
        }
        sort(sub.begin(), sub.end(), greater<long long>());
        if (S[x][y] == '#') res = sub[0];
        else if (S[x][y] == '+') res = sub[0] + sub[1];
        else if (S[x][y] == '-') res = sub[0] - sub[1];
        else if (S[x][y] == '*') res = sub[0] * sub[1];
        else res = sub[0] / sub[1];
        return res;
    };
    cout << rec(rec, sx, sy) << endl;
}