[CPB] SEARCH

by | Oct 27, 2025 | Hướng dẫn giải | 0 comments

Mô tả ngắn gọn

  • Bản đồ là ma trận $R \times C$ với ký tự '.' đi được, 'X' không đi được, và vị trí xuất phát được đánh dấu '*'. Xe chỉ di chuyển theo 4 hướng cơ bản (NORTH, SOUTH, WEST, EAST).
  • Dãy hành trình gồm $N$ hướng; với mỗi hướng, Ralph có thể đi một hoặc nhiều ô theo cùng hướng đó (liên tiếp, không xuyên chướng ngại).
  • Yêu cầu in lại bản đồ, thay '*' bằng tập mọi vị trí cuối cùng có thể có sau khi thực hiện tuần tự $N$ hướng.

Mô hình hóa theo gợi ý $(i,j,k)$

Xây dựng đồ thị $G$ trên không gian trạng thái 3 chiều:

  • Đỉnh là bộ $(i,j,k)$: ở hàng $i$, cột $j$ sau khi đã đi xong $k$ hướng đầu ($0 \le k \le N$).
  • Từ đỉnh $(i,j,k)$, theo hướng thứ $k!+!1$ trong input, có các cung đến mọi $(i’,j’,k!+!1)$ mà $(i’,j’)$ nằm trên tia thẳng xuất phát từ $(i,j)$ theo hướng đó, với số bước $\ge 1$, và đường đi không chạm ô 'X' (chỉ đi trên '.' hoặc vị trí xuất phát hợp lệ).
  • Đỉnh gốc: $(r_0,c_0,0)$ là vị trí '*' ban đầu.
  • Đáp án: mọi trạng thái $(i,j,N)$ đạt được sau $N$ lần nở theo luật trên.

Do các cung chỉ đi từ lớp $k$ sang lớp $k!+!1$, đồ thị là có hướng theo lớp ⇒ có thể duyệt theo BFS theo lớp (thực chất là “DP theo lớp” / “multi-source expansion”):
$$
S_0={(r_0,c_0)},\quad
S_{k+1}=\bigcup_{(i,j)\in S_k}\ \text{AllEndpoints}\big((i,j),\ \text{dir}[k+1]\big).
$$

Thuật toán

Ý tưởng

  1. Đọc lưới, tìm $(r_0,c_0)$ là vị trí '*'.
  2. Đọc $N$ và dãy hướng (không có hai hướng liên tiếp trùng nhau – thông tin này không làm thay đổi thuật toán nhưng đúng theo đề).
  3. Khởi tạo tập $S={(r_0,c_0)}$.
  4. Với từng hướng $d$ trong dãy (theo thứ tự):
    • Tạo tập mới $T=\varnothing$ và mảng đánh dấu vis cho lớp mới.
    • Với mỗi $(i,j)\in S$, trượt theo hướng $d$: tăng dần số bước $t=1,2,\dots$ cho đến khi ra biên hoặc gặp 'X'; với mỗi điểm trung gian hợp lệ $(i’,j’)$ gặp được, thêm vào $T$ (tránh trùng bằng vis).
    • Gán $S \leftarrow T`.
  5. Sau $N$ hướng, $S$ là tập trạng thái cuối; lập bản đồ kết quả: giữ nguyên 'X', biến tất cả ô khác thành '.', rồi đặt '*' tại mọi ô trong $S$.

Tính đúng đắn (ngắn gọn)

  • Mỗi bước hướng là các cạnh từ lớp $k$ sang lớp $k!+!1$ đến mọi điểm kết thúc hợp lệ khi đi thẳng ≥ 1 ô. Việc “trượt theo tia” bao trùm toàn bộ lựa chọn “bao nhiêu ô” theo đề.
  • Duyệt theo lớp đảm bảo đúng thứ tự hướng; gộp (hợp) từ mọi nguồn trong lớp trước đảm bảo ta thu được tất cả vị trí khả dĩ của lớp sau.

Độ phức tạp

  • Gọi $V=RC\le 2500$, $N\le 1000$. Mỗi lớp, mỗi nguồn có thể “trượt” tối đa $O(\min(R,C))$.
  • Thực tế chặt: $O(N\cdot V)$–$O(N\cdot V\cdot \text{ray})$ tùy cài đặt; với $R,C\le 50$ chạy rất thoải mái.

Bài giải tham khảo

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

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

    int R, C;
    if (!(cin >> R >> C)) return 0;
    vector<string> g(R);
    for (int i = 0; i < R; ++i) cin >> g[i];

    int sr = -1, sc = -1;
    for (int i = 0; i < R; ++i)
        for (int j = 0; j < C; ++j)
            if (g[i][j] == '*') { sr = i; sc = j; }

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

    auto inb = [&](int r, int c){ return 0 <= r && r < R && 0 <= c && c < C; };

    // ánh xạ hướng sang vector (dr,dc)
    auto dvec = [&](const string& s){
        if (s == "NORTH") return pair<int,int>{-1, 0};
        if (s == "SOUTH") return pair<int,int>{ 1, 0};
        if (s == "WEST")  return pair<int,int>{ 0,-1};
        /* EAST */        return pair<int,int>{ 0, 1};
    };

    // S_k: tập vị trí có thể có sau k hướng
    vector<pair<int,int>> S;
    S.emplace_back(sr, sc);

    for (int k = 0; k < N; ++k) {
        auto [dr, dc] = dvec(dir[k]);
        vector<vector<char>> vis(R, vector<char>(C, 0));
        vector<pair<int,int>> T;

        for (auto [r, c] : S) {
            int nr = r + dr, nc = c + dc;
            // phải đi ít nhất 1 ô; dừng khi chạm biên hoặc 'X'
            while (inb(nr, nc) && g[nr][nc] != 'X') {
                if (!vis[nr][nc]) {
                    vis[nr][nc] = 1;
                    T.emplace_back(nr, nc);
                }
                nr += dr; nc += dc;
            }
        }
        // không còn vị trí hợp lệ -> không thể đi tiếp (tập rỗng)
        S.swap(T);
    }

    // In bản đồ: '*' ở mọi vị trí cuối cùng; các ô khác không phải 'X' đặt '.'
    vector<string> out = g;
    for (int i = 0; i < R; ++i)
        for (int j = 0; j < C; ++j)
            if (out[i][j] != 'X') out[i][j] = '.';
    for (auto [r, c] : S) out[r][c] = '*';

    for (int i = 0; i < R; ++i) cout << out[i] << "\n";
    return 0;
}

Chú ý:

  • Vị trí '*' ban đầu được phép đi qua (xem như ô đi được).
  • Mỗi hướng bắt buộc đi ít nhất một ô (vòng while bắt đầu từ $t=1$).
  • Đầu ra giữ nguyên 'X', đánh dấu '*' cho mọi vị trí lớp $N$ (có thể có nhiều dấu '*').