A1807 SEARCH

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

// SEARCH：汽车按给定方向序列行驶，求它最终所有可能停在哪里。
//
// 每个方向上，汽车要沿该方向走**一格以上**（可以走任意多格），
// 遇到 X 就走不过去。于是「当前可能在 p」可以扩展成
// 「沿该方向、直到被 X 挡住之前的所有可通行格子」。
//
// 用扫描线做这个扩展（每个方向 O(R*C)）：
//   NORTH：从下往上扫每一列，open 表示「下方存在一个可能位置，且中间没有 X」
//   SOUTH：从上往下扫每一列
//   WEST ：从右往左扫每一行
//   EAST ：从左往右扫每一行
// 扫到某个格子时，先用 open 决定它能不能成为新的可能位置（必须至少走一格，
// 所以要用**更新前**的 open），再把 cur 加进 open。

const int MAXN = 55;

int R, C;
char g[MAXN][MAXN];
bool cur[MAXN][MAXN], nxt[MAXN][MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> R >> C;
    int sx = -1, sy = -1;
    for (int r = 0; r < R; r++) {
        cin >> g[r];
        for (int c = 0; c < C; c++) {
            if (g[r][c] == '*') {
                sx = r;
                sy = c;
            }
        }
    }

    int N;
    cin >> N;
    vector<string> dirs(N);
    for (int i = 0; i < N; i++) cin >> dirs[i];

    memset(cur, 0, sizeof(cur));
    cur[sx][sy] = true;

    for (int k = 0; k < N; k++) {
        const string& d = dirs[k];
        memset(nxt, 0, sizeof(nxt));

        if (d == "NORTH") {
            for (int c = 0; c < C; c++) {
                bool open = false;
                for (int r = R - 1; r >= 0; r--) {
                    if (g[r][c] == 'X') { open = false; continue; }
                    nxt[r][c] = open;
                    if (cur[r][c]) open = true;
                }
            }
        } else if (d == "SOUTH") {
            for (int c = 0; c < C; c++) {
                bool open = false;
                for (int r = 0; r < R; r++) {
                    if (g[r][c] == 'X') { open = false; continue; }
                    nxt[r][c] = open;
                    if (cur[r][c]) open = true;
                }
            }
        } else if (d == "WEST") {
            for (int r = 0; r < R; r++) {
                bool open = false;
                for (int c = C - 1; c >= 0; c--) {
                    if (g[r][c] == 'X') { open = false; continue; }
                    nxt[r][c] = open;
                    if (cur[r][c]) open = true;
                }
            }
        } else { // EAST
            for (int r = 0; r < R; r++) {
                bool open = false;
                for (int c = 0; c < C; c++) {
                    if (g[r][c] == 'X') { open = false; continue; }
                    nxt[r][c] = open;
                    if (cur[r][c]) open = true;
                }
            }
        }

        memcpy(cur, nxt, sizeof(cur));
    }

    for (int r = 0; r < R; r++) {
        for (int c = 0; c < C; c++) {
            char ch = g[r][c];
            if (ch == '*') ch = '.';
            if (cur[r][c]) ch = '*';
            cout << ch;
        }
        cout << "\n";
    }
    return 0;
}