[AtCoder] ABC 182 E – Akari

2020年11月9日2020年12月12日

問題

方針

\( H \) 行 \( W \) 列の情報を \( g(i, j) \) とします。\( g(i, j) = 1 \) のとき電球があり、\( g(i, j) = 2 \) のとき壁があるとします。ここで、\( g(i, j) = 1\) のとき、\( g(i, j) = 2 \) となるまで、\( j \) の値を増加し電球の届く範囲を記録します。壁にぶつからないうちに電球を見つけた場合は、その電球から同じ方向のマスを追加で調べる必要はありません。

これを、上下左右の \( 4 \) 方向全探索します。

コード

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

int main() {
    int H, W, N, M;
    cin >> H >> W >> N >> M;
    int A[N], B[N], C[M], D[M];
    int g[H][W]{};
    int v[H][W]{};
    for (int i = 0; i < N; i++) {
        cin >> A[i] >> B[i];
        A[i]--;
        B[i]--;
        g[A[i]][B[i]] = 1;
        v[A[i]][B[i]] = 1;
    }
    for (int i = 0; i < M; i++) {
        cin >> C[i] >> D[i];
        C[i]--;
        D[i]--;
        g[C[i]][D[i]] = 2;
    }
    
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (g[i][j] == 1) {
                while (j < W && g[i][j] != 2) {
                    v[i][j] = 1;
                    j++;
                } 
            }
        }
    }
    for (int i = 0; i < H; i++) {
        for (int j = W - 1; j >= 0; j--) {
            if (g[i][j] == 1) {
                while (j >= 0 && g[i][j] != 2) {
                    v[i][j] = 1;
                    j--;
                } 
            }
        }
    }
    for (int i = 0; i < W; i++) {
        for (int j = 0; j < H; j++) {
            if (g[j][i] == 1) {
                while (j < H && g[j][i] != 2) {
                    v[j][i] = 1;
                    j++;
                }
            }
        }
    }
    for (int i = 0; i < W; i++) {
        for (int j = H - 1; j >= 0; j--) {
            if (g[j][i] == 1) {
                while (j >= 0 && g[j][i] != 2) {
                    v[j][i] = 1;
                    j--;
                }
            }
        }
    }
    int cnt = 0;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (v[i][j] == 1) cnt++;
        }
    }
    cout << cnt << "\n";
    return 0;
}