C++ の動作確認をしてみた（７６）

C++の練習を兼ねて, AtCoder Beginner Contest 088 の問題D (D – Grid Repainting) を解いてみた.

■感想.
1. どこかで類題を見た記憶があったので, 探したところ, AtCoder Typical Contest 002 の A – 幅優先探索に似ていることが分かった.
2. 幅優先探索(BFS) を復習出来たので, 良かったと思う.

本家のサイトAtcoder Beginner Contest 088 解説をご覧下さい.

■C++版プログラム(問題D／AC版).

// A - 幅優先探索.
// https://atcoder.jp/contests/atc002/tasks/abc007_3
// -> 上記の解答を, 少し修正した版.
#include <bits/stdc++.h>
using namespace std;
// constexpr int MAX = 400;
constexpr int MAX = 2601;
constexpr int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
int R, C;
int sx, sy, gx, gy;
int board[MAX];
int memo[MAX];

// 幅優先探索.
// https://ja.wikipedia.org/wiki/幅優先探索
// 迷路を幅優先探索する.
// ※bfsの動作確認用.
// @param s: 探索開始地点の迷路上の座標.
// @return: 特に無し.
void bfs(int s){
    
    // 1. 空のキュー.
    queue<int> q;
    
    // 2. 訪問済みフラグ設定.
    // ※スタート地点は, 距離ゼロを指定.
    memo[s] = 0;
    
    // 3. 探索地点 s をキュー q に追加.
    q.push(s);
    while(!q.empty()){
        // 4. キューから取り出す.
        int v = q.front();
        q.pop();
        // 5. 取り出した要素を処理.
        // x: 列方向, y: 行方向 で考える.
        int nx, ny, n;
        int cx = v % C , cy = v / C;
        for(int i = 0; i < 4; ++i){
            nx = cx + dx[i];
            ny = cy + dy[i];
            n = nx + ny * C;
            // cout << "cx=" << cx << " nx=" << nx  << " cy=" << cy << " ny=" << ny << " n=" << n << " c=" << c << endl;
            // 6. 訪問不可能なマス であれば, 処理をスキップ.
            if(n < 0 || nx < 0 || nx >= C || ny < 0 || ny >= R) continue;
            if(board[n] == '#')                                 continue;
            
            // 7. 訪問先のマスで, 訪問可能 かつ スタート地点でない かつ 未訪問 であれば, 訪問済み(※最短ルート)を設定.
            if(board[n] == '.' && n != s && memo[n] == 0) memo[n] = memo[v] + 1, q.push(n);
        }
    }
    return;
}

int main() {
    
    // 1. 入力情報取得.
    cin >> R >> C;
    sy = 1, sx = 1, gy = R, gx = C;
    sy--, sx--, gy--, gx--;
    int dot = 0;
    for(int i = 0; i < R; ++i){
        string s;
        cin >> s;
        for(int j = 0; j < C; ++j){
            board[i * C + j] = s[j];
            // 白マスの個数をカウント.
            if(s[j] == '.') dot++;
        }
    }
    
    // 2. 探索を開始し, 探索距離を更新.
    bfs(sy * C + sx);
    // ゴールまでの最短距離(※ゼロの場合は, ゴールに辿り着けないと判定).
    int dist = memo[gy * C + gx];
    // for(int i = 0; i < R; ++i){
    //     for(int j = 0; j < C; ++j){
    //         cout << memo[i * C + j] << " ";
    //     }
    //     cout << endl;
    // }
    
    // 3. 出力.
    int ans = -1;
    // マス(1, 1), マス(H, W) の 色 は 変更できないので, (dist + 1) を 引く形に修正.
    if(dist > 0) ans = dot - (dist + 1);
    cout << ans << endl;
    return 0;
    
}

// A - 幅優先探索.

// https://atcoder.jp/contests/atc002/tasks/abc007_3

// -> 上記の解答を, 少し修正した版.

#include <bits/stdc++.h>

using namespace std;

// constexpr int MAX = 400;

constexpr int MAX = 2601;

constexpr int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};

int R, C;

int sx, sy, gx, gy;

int board[MAX];

int memo[MAX];

// 幅優先探索.

// https://ja.wikipedia.org/wiki/幅優先探索

// 迷路を幅優先探索する.

// ※bfsの動作確認用.

// @param s: 探索開始地点の迷路上の座標.

// @return: 特に無し.

void bfs(int s){

// 1. 空のキュー.

queue<int> q;

// 2. 訪問済みフラグ設定.

// ※スタート地点は, 距離ゼロを指定.

memo[s] = 0;

// 3. 探索地点 s をキュー q に追加.

q.push(s);

while(!q.empty()){

// 4. キューから取り出す.

int v = q.front();

q.pop();

// 5. 取り出した要素を処理.

// x: 列方向, y: 行方向で考える.

int nx, ny, n;

int cx = v % C , cy = v / C;

for(int i = 0; i < 4; ++i){

nx = cx + dx[i];

ny = cy + dy[i];

n = nx + ny * C;

// cout << "cx=" << cx << " nx=" << nx << " cy=" << cy << " ny=" << ny << " n=" << n << " c=" << c << endl;

// 6. 訪問不可能なマスであれば, 処理をスキップ.

if(n < 0 || nx < 0 || nx >= C || ny < 0 || ny >= R) continue;

if(board[n] == '#') continue;

// 7. 訪問先のマスで, 訪問可能かつスタート地点でないかつ未訪問であれば, 訪問済み(※最短ルート)を設定.

if(board[n] == '.' && n != s && memo[n] == 0) memo[n] = memo[v] + 1, q.push(n);

}

return;

}

int main() {

// 1. 入力情報取得.

cin >> R >> C;

sy = 1, sx = 1, gy = R, gx = C;

sy--, sx--, gy--, gx--;

int dot = 0;

for(int i = 0; i < R; ++i){

string s;

cin >> s;

for(int j = 0; j < C; ++j){

board[i * C + j] = s[j];

// 白マスの個数をカウント.

if(s[j] == '.') dot++;

}

// 2. 探索を開始し, 探索距離を更新.

bfs(sy * C + sx);

// ゴールまでの最短距離(※ゼロの場合は, ゴールに辿り着けないと判定).

int dist = memo[gy * C + gx];

// for(int i = 0; i < R; ++i){

// for(int j = 0; j < C; ++j){

// cout << memo[i * C + j] << " ";

// }

// cout << endl;

// }

// 3. 出力.

int ans = -1;

// マス(1, 1), マス(H, W) の色は変更できないので, (dist + 1) を引く形に修正.

if(dist > 0) ans = dot - (dist + 1);

cout << ans << endl;

return 0;

}

[入力例]
2 2
..
..

[出力例(debug版)]
0 1 
1 2 
1

[入力例]
3 4
..#.
..#.
.#..

[出力例(debug版)]
0 1 0 0 
1 2 0 0 
2 0 0 0 
-1

[入力例]
3 3
..#
#..
...

[出力例(debug版)]
0 1 0 
0 2 3 
4 3 4 
2
※AtCoderテストケースより

[入力例]
10 37
.....................................
...#...####...####..###...###...###..
..#.#..#...#.##....#...#.#...#.#...#.
..#.#..#...#.#.....#...#.#...#.#...#.
.#...#.#..##.#.....#...#.#.###.#.###.
.#####.####..#.....#...#..##....##...
.#...#.#...#.#.....#...#.#...#.#...#.
.#...#.#...#.##....#...#.#...#.#...#.
.#...#.####...####..###...###...###..
.....................................

[出力例(debug版)]
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 
1 2 3 0 5 6 7 0 0 0 0 12 13 14 0 0 0 0 19 20 0 0 0 24 25 26 0 0 0 30 31 32 0 0 0 36 37 
2 3 0 0 0 7 8 0 0 0 0 0 14 0 0 23 22 21 20 0 0 0 0 0 26 0 0 0 0 0 32 0 0 0 0 0 38 
3 4 0 0 0 8 9 0 0 0 0 0 15 0 25 24 23 22 21 0 0 0 0 0 27 0 0 0 0 0 33 0 0 0 0 0 39 
4 0 0 0 0 0 10 0 0 0 0 0 16 0 26 25 24 23 22 0 0 0 0 0 28 0 0 0 0 0 34 0 0 0 0 0 40 
5 0 0 0 0 0 11 0 0 0 0 18 17 0 27 26 25 24 23 0 0 0 0 0 29 30 0 0 37 36 35 36 0 0 43 42 41 
6 0 14 15 16 0 12 0 0 0 0 0 18 0 28 27 26 25 24 0 0 0 0 0 30 0 40 39 38 0 36 0 46 45 44 0 42 
7 0 13 14 15 0 13 0 0 0 0 0 19 0 0 28 27 26 25 0 0 0 0 0 31 0 41 40 39 0 37 0 47 46 45 0 43 
8 0 12 13 14 0 14 0 0 0 0 21 20 21 0 0 0 0 26 27 0 0 0 33 32 33 0 0 0 39 38 39 0 0 0 45 44 
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 
209
※AtCoderテストケースより

[入力例]
50 50
..................................................
...#...####...####.#####..#####.######.######.....
..#.#..#...#.##....#....#.#.....#......#....#.....
..#.#..#...#.#.....#....#.#.....#......#....#.....
.#...#.#..##.#.....#....#.#####.#####..#..........
.#####.####..#.....#....#.#.....#......#..###.....
.#...#.#...#.#.....#....#.#.....#......#....#.....
.#...#.#...#.##....#....#.#.....#......#....#.....
.#...#.####...####.#####..#####.#......######.....
..................................................
..................................................
...#...####...####.#####..#####.######.######.....
..#.#..#...#.##....#....#.#.....#......#....#.....
..#.#..#...#.#.....#....#.#.....#......#....#.....
.#...#.#..##.#.....#....#.#####.#####..#..........
.#####.####..#.....#....#.#.....#......#..###.....
.#...#.#...#.#.....#....#.#.....#......#....#.....
.#...#.#...#.##....#....#.#.....#......#....#.....
.#...#.####...####.#####..#####.#......######.....
..................................................
..................................................
...#...####...####.#####..#####.######.######.....
..#.#..#...#.##....#....#.#.....#......#....#.....
..#.#..#...#.#.....#....#.#.....#......#....#.....
.#...#.#..##.#.....#....#.#####.#####..#..........
.#####.####..#.....#....#.#.....#......#..###.....
.#...#.#...#.#.....#....#.#.....#......#....#.....
.#...#.#...#.##....#....#.#.....#......#....#.....
.#...#.####...####.#####..#####.#......######.....
..................................................
..................................................
...#...####...####.#####..#####.######.######.....
..#.#..#...#.##....#....#.#.....#......#....#.....
..#.#..#...#.#.....#....#.#.....#......#....#.....
.#...#.#..##.#.....#....#.#####.#####..#..........
.#####.####..#.....#....#.#.....#......#..###.....
.#...#.#...#.#.....#....#.#.....#......#....#.....
.#...#.#...#.##....#....#.#.....#......#....#.....
.#...#.####...####.#####..#####.#......######.....
..................................................
..................................................
...#...####...####.#####..#####.######.######.....
..#.#..#...#.##....#....#.#.....#......#....#.....
..#.#..#...#.#.....#....#.#.....#......#....#.....
.#...#.#..##.#.....#....#.#####.#####..#..........
.#####.####..#.....#....#.#.....#......#..###.....
.#...#.#...#.#.....#....#.#.....#......#....#.....
.#...#.#...#.##....#....#.#.....#......#....#.....
.#...#.####...####.#####..#####.#......######.....
..................................................

[出力例(debug版)]
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 
1 2 3 0 5 6 7 0 0 0 0 12 13 14 0 0 0 0 19 0 0 0 0 0 25 26 0 0 0 0 0 32 0 0 0 0 0 0 39 0 0 0 0 0 0 46 47 48 49 50 
2 3 0 0 0 7 8 0 0 0 0 0 14 0 0 23 22 21 20 0 0 0 0 0 0 27 0 37 36 35 34 33 0 45 44 43 42 41 40 0 56 55 54 53 0 47 48 49 50 51 
3 4 0 0 0 8 9 0 0 0 0 0 15 0 25 24 23 22 21 0 0 0 0 0 0 28 0 38 37 36 35 34 0 46 45 44 43 42 41 0 55 54 53 52 0 48 49 50 51 52 
4 0 0 0 0 0 10 0 0 0 0 0 16 0 26 25 24 23 22 0 0 0 0 0 0 29 0 0 0 0 0 35 0 0 0 0 0 43 42 0 54 53 52 51 50 49 50 51 52 53 
5 0 0 0 0 0 11 0 0 0 0 18 17 0 27 26 25 24 23 0 0 0 0 0 0 30 0 40 39 38 37 36 0 46 47 46 45 44 43 0 55 54 0 0 0 50 51 52 53 54 
6 0 14 15 16 0 12 0 0 0 0 0 18 0 28 27 26 25 24 0 0 0 0 0 0 31 0 41 40 39 38 37 0 45 46 47 46 45 44 0 56 55 56 57 0 51 52 53 54 55 
7 0 13 14 15 0 13 0 0 0 0 0 19 0 0 28 27 26 25 0 0 0 0 0 0 32 0 42 41 40 39 38 0 44 45 46 47 46 45 0 57 56 57 58 0 52 53 54 55 56 
8 0 12 13 14 0 14 0 0 0 0 21 20 21 0 0 0 0 26 0 0 0 0 0 34 33 0 0 0 0 0 39 0 43 44 45 46 47 46 0 0 0 0 0 0 53 54 55 56 57 
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 
11 12 13 0 15 16 17 0 0 0 0 22 23 24 0 0 0 0 29 0 0 0 0 0 35 36 0 0 0 0 0 42 0 0 0 0 0 0 49 0 0 0 0 0 0 56 57 58 59 60 
12 13 0 0 0 17 18 0 0 0 0 0 24 0 0 33 32 31 30 0 0 0 0 0 0 37 0 47 46 45 44 43 0 55 54 53 52 51 50 0 66 65 64 63 0 57 58 59 60 61 
13 14 0 0 0 18 19 0 0 0 0 0 25 0 35 34 33 32 31 0 0 0 0 0 0 38 0 48 47 46 45 44 0 56 55 54 53 52 51 0 65 64 63 62 0 58 59 60 61 62 
14 0 0 0 0 0 20 0 0 0 0 0 26 0 36 35 34 33 32 0 0 0 0 0 0 39 0 0 0 0 0 45 0 0 0 0 0 53 52 0 64 63 62 61 60 59 60 61 62 63 
15 0 0 0 0 0 21 0 0 0 0 28 27 0 37 36 35 34 33 0 0 0 0 0 0 40 0 50 49 48 47 46 0 56 57 56 55 54 53 0 65 64 0 0 0 60 61 62 63 64 
16 0 24 25 26 0 22 0 0 0 0 0 28 0 38 37 36 35 34 0 0 0 0 0 0 41 0 51 50 49 48 47 0 55 56 57 56 55 54 0 66 65 66 67 0 61 62 63 64 65 
17 0 23 24 25 0 23 0 0 0 0 0 29 0 0 38 37 36 35 0 0 0 0 0 0 42 0 52 51 50 49 48 0 54 55 56 57 56 55 0 67 66 67 68 0 62 63 64 65 66 
18 0 22 23 24 0 24 0 0 0 0 31 30 31 0 0 0 0 36 0 0 0 0 0 44 43 0 0 0 0 0 49 0 53 54 55 56 57 56 0 0 0 0 0 0 63 64 65 66 67 
19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 
20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 
21 22 23 0 25 26 27 0 0 0 0 32 33 34 0 0 0 0 39 0 0 0 0 0 45 46 0 0 0 0 0 52 0 0 0 0 0 0 59 0 0 0 0 0 0 66 67 68 69 70 
22 23 0 0 0 27 28 0 0 0 0 0 34 0 0 43 42 41 40 0 0 0 0 0 0 47 0 57 56 55 54 53 0 65 64 63 62 61 60 0 76 75 74 73 0 67 68 69 70 71 
23 24 0 0 0 28 29 0 0 0 0 0 35 0 45 44 43 42 41 0 0 0 0 0 0 48 0 58 57 56 55 54 0 66 65 64 63 62 61 0 75 74 73 72 0 68 69 70 71 72 
24 0 0 0 0 0 30 0 0 0 0 0 36 0 46 45 44 43 42 0 0 0 0 0 0 49 0 0 0 0 0 55 0 0 0 0 0 63 62 0 74 73 72 71 70 69 70 71 72 73 
25 0 0 0 0 0 31 0 0 0 0 38 37 0 47 46 45 44 43 0 0 0 0 0 0 50 0 60 59 58 57 56 0 66 67 66 65 64 63 0 75 74 0 0 0 70 71 72 73 74 
26 0 34 35 36 0 32 0 0 0 0 0 38 0 48 47 46 45 44 0 0 0 0 0 0 51 0 61 60 59 58 57 0 65 66 67 66 65 64 0 76 75 76 77 0 71 72 73 74 75 
27 0 33 34 35 0 33 0 0 0 0 0 39 0 0 48 47 46 45 0 0 0 0 0 0 52 0 62 61 60 59 58 0 64 65 66 67 66 65 0 77 76 77 78 0 72 73 74 75 76 
28 0 32 33 34 0 34 0 0 0 0 41 40 41 0 0 0 0 46 0 0 0 0 0 54 53 0 0 0 0 0 59 0 63 64 65 66 67 66 0 0 0 0 0 0 73 74 75 76 77 
29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 
30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 
31 32 33 0 35 36 37 0 0 0 0 42 43 44 0 0 0 0 49 0 0 0 0 0 55 56 0 0 0 0 0 62 0 0 0 0 0 0 69 0 0 0 0 0 0 76 77 78 79 80 
32 33 0 0 0 37 38 0 0 0 0 0 44 0 0 53 52 51 50 0 0 0 0 0 0 57 0 67 66 65 64 63 0 75 74 73 72 71 70 0 86 85 84 83 0 77 78 79 80 81 
33 34 0 0 0 38 39 0 0 0 0 0 45 0 55 54 53 52 51 0 0 0 0 0 0 58 0 68 67 66 65 64 0 76 75 74 73 72 71 0 85 84 83 82 0 78 79 80 81 82 
34 0 0 0 0 0 40 0 0 0 0 0 46 0 56 55 54 53 52 0 0 0 0 0 0 59 0 0 0 0 0 65 0 0 0 0 0 73 72 0 84 83 82 81 80 79 80 81 82 83 
35 0 0 0 0 0 41 0 0 0 0 48 47 0 57 56 55 54 53 0 0 0 0 0 0 60 0 70 69 68 67 66 0 76 77 76 75 74 73 0 85 84 0 0 0 80 81 82 83 84 
36 0 44 45 46 0 42 0 0 0 0 0 48 0 58 57 56 55 54 0 0 0 0 0 0 61 0 71 70 69 68 67 0 75 76 77 76 75 74 0 86 85 86 87 0 81 82 83 84 85 
37 0 43 44 45 0 43 0 0 0 0 0 49 0 0 58 57 56 55 0 0 0 0 0 0 62 0 72 71 70 69 68 0 74 75 76 77 76 75 0 87 86 87 88 0 82 83 84 85 86 
38 0 42 43 44 0 44 0 0 0 0 51 50 51 0 0 0 0 56 0 0 0 0 0 64 63 0 0 0 0 0 69 0 73 74 75 76 77 76 0 0 0 0 0 0 83 84 85 86 87 
39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 
40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 
41 42 43 0 45 46 47 0 0 0 0 52 53 54 0 0 0 0 59 0 0 0 0 0 65 66 0 0 0 0 0 72 0 0 0 0 0 0 79 0 0 0 0 0 0 86 87 88 89 90 
42 43 0 0 0 47 48 0 0 0 0 0 54 0 0 63 62 61 60 0 0 0 0 0 0 67 0 77 76 75 74 73 0 85 84 83 82 81 80 0 96 95 94 93 0 87 88 89 90 91 
43 44 0 0 0 48 49 0 0 0 0 0 55 0 65 64 63 62 61 0 0 0 0 0 0 68 0 78 77 76 75 74 0 86 85 84 83 82 81 0 95 94 93 92 0 88 89 90 91 92 
44 0 0 0 0 0 50 0 0 0 0 0 56 0 66 65 64 63 62 0 0 0 0 0 0 69 0 0 0 0 0 75 0 0 0 0 0 83 82 0 94 93 92 91 90 89 90 91 92 93 
45 0 0 0 0 0 51 0 0 0 0 58 57 0 67 66 65 64 63 0 0 0 0 0 0 70 0 80 79 78 77 76 0 86 87 86 85 84 83 0 95 94 0 0 0 90 91 92 93 94 
46 0 54 55 56 0 52 0 0 0 0 0 58 0 68 67 66 65 64 0 0 0 0 0 0 71 0 81 80 79 78 77 0 85 86 87 86 85 84 0 96 95 96 97 0 91 92 93 94 95 
47 0 53 54 55 0 53 0 0 0 0 0 59 0 0 68 67 66 65 0 0 0 0 0 0 72 0 82 81 80 79 78 0 84 85 86 87 86 85 0 97 96 97 98 0 92 93 94 95 96 
48 0 52 53 54 0 54 0 0 0 0 61 60 61 0 0 0 0 66 0 0 0 0 0 74 73 0 0 0 0 0 79 0 83 84 85 86 87 86 0 0 0 0 0 0 93 94 95 96 97 
49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 
1696

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

[入力例]

2 2

[出力例(debug版)]

0 1

1 2

[入力例]

3 4

..#.

.#..

[出力例(debug版)]

0 1 0 0

1 2 0 0

2 0 0 0

-1

[入力例]

3 3

..#

#..

...

[出力例(debug版)]

0 1 0

0 2 3

4 3 4

※AtCoderテストケースより

[入力例]

10 37

.....................................

...#...####...####..###...###...###..

..#.#..#...#.##....#...#.#...#.#...#.

..#.#..#...#.#.....#...#.#...#.#...#.

.#...#.#..##.#.....#...#.#.###.#.###.

.#####.####..#.....#...#..##....##...

.#...#.#...#.#.....#...#.#...#.#...#.

.#...#.#...#.##....#...#.#...#.#...#.

.#...#.####...####..###...###...###..

.....................................

[出力例(debug版)]

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

1 2 3 0 5 6 7 0 0 0 0 12 13 14 0 0 0 0 19 20 0 0 0 24 25 26 0 0 0 30 31 32 0 0 0 36 37

2 3 0 0 0 7 8 0 0 0 0 0 14 0 0 23 22 21 20 0 0 0 0 0 26 0 0 0 0 0 32 0 0 0 0 0 38

3 4 0 0 0 8 9 0 0 0 0 0 15 0 25 24 23 22 21 0 0 0 0 0 27 0 0 0 0 0 33 0 0 0 0 0 39

4 0 0 0 0 0 10 0 0 0 0 0 16 0 26 25 24 23 22 0 0 0 0 0 28 0 0 0 0 0 34 0 0 0 0 0 40

5 0 0 0 0 0 11 0 0 0 0 18 17 0 27 26 25 24 23 0 0 0 0 0 29 30 0 0 37 36 35 36 0 0 43 42 41

6 0 14 15 16 0 12 0 0 0 0 0 18 0 28 27 26 25 24 0 0 0 0 0 30 0 40 39 38 0 36 0 46 45 44 0 42

7 0 13 14 15 0 13 0 0 0 0 0 19 0 0 28 27 26 25 0 0 0 0 0 31 0 41 40 39 0 37 0 47 46 45 0 43

8 0 12 13 14 0 14 0 0 0 0 21 20 21 0 0 0 0 26 27 0 0 0 33 32 33 0 0 0 39 38 39 0 0 0 45 44

9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

209

※AtCoderテストケースより

[入力例]

50 50

..................................................

...#...####...####.#####..#####.######.######.....

..#.#..#...#.##....#....#.#.....#......#....#.....

..#.#..#...#.#.....#....#.#.....#......#....#.....

.#...#.#..##.#.....#....#.#####.#####..#..........

.#####.####..#.....#....#.#.....#......#..###.....

.#...#.#...#.#.....#....#.#.....#......#....#.....

.#...#.#...#.##....#....#.#.....#......#....#.....

.#...#.####...####.#####..#####.#......######.....

..................................................

...#...####...####.#####..#####.######.######.....

..#.#..#...#.##....#....#.#.....#......#....#.....

..#.#..#...#.#.....#....#.#.....#......#....#.....

.#...#.#..##.#.....#....#.#####.#####..#..........

.#####.####..#.....#....#.#.....#......#..###.....

.#...#.#...#.#.....#....#.#.....#......#....#.....

.#...#.#...#.##....#....#.#.....#......#....#.....

.#...#.####...####.#####..#####.#......######.....

..................................................

...#...####...####.#####..#####.######.######.....

..#.#..#...#.##....#....#.#.....#......#....#.....

..#.#..#...#.#.....#....#.#.....#......#....#.....

.#...#.#..##.#.....#....#.#####.#####..#..........

.#####.####..#.....#....#.#.....#......#..###.....

.#...#.#...#.#.....#....#.#.....#......#....#.....

.#...#.#...#.##....#....#.#.....#......#....#.....

.#...#.####...####.#####..#####.#......######.....

..................................................

...#...####...####.#####..#####.######.######.....

..#.#..#...#.##....#....#.#.....#......#....#.....

..#.#..#...#.#.....#....#.#.....#......#....#.....

.#...#.#..##.#.....#....#.#####.#####..#..........

.#####.####..#.....#....#.#.....#......#..###.....

.#...#.#...#.#.....#....#.#.....#......#....#.....

.#...#.#...#.##....#....#.#.....#......#....#.....

.#...#.####...####.#####..#####.#......######.....

..................................................

...#...####...####.#####..#####.######.######.....

..#.#..#...#.##....#....#.#.....#......#....#.....

..#.#..#...#.#.....#....#.#.....#......#....#.....

.#...#.#..##.#.....#....#.#####.#####..#..........

.#####.####..#.....#....#.#.....#......#..###.....

.#...#.#...#.#.....#....#.#.....#......#....#.....

.#...#.#...#.##....#....#.#.....#......#....#.....

.#...#.####...####.#####..#####.#......######.....

..................................................

[出力例(debug版)]

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

1 2 3 0 5 6 7 0 0 0 0 12 13 14 0 0 0 0 19 0 0 0 0 0 25 26 0 0 0 0 0 32 0 0 0 0 0 0 39 0 0 0 0 0 0 46 47 48 49 50

2 3 0 0 0 7 8 0 0 0 0 0 14 0 0 23 22 21 20 0 0 0 0 0 0 27 0 37 36 35 34 33 0 45 44 43 42 41 40 0 56 55 54 53 0 47 48 49 50 51

3 4 0 0 0 8 9 0 0 0 0 0 15 0 25 24 23 22 21 0 0 0 0 0 0 28 0 38 37 36 35 34 0 46 45 44 43 42 41 0 55 54 53 52 0 48 49 50 51 52

4 0 0 0 0 0 10 0 0 0 0 0 16 0 26 25 24 23 22 0 0 0 0 0 0 29 0 0 0 0 0 35 0 0 0 0 0 43 42 0 54 53 52 51 50 49 50 51 52 53

5 0 0 0 0 0 11 0 0 0 0 18 17 0 27 26 25 24 23 0 0 0 0 0 0 30 0 40 39 38 37 36 0 46 47 46 45 44 43 0 55 54 0 0 0 50 51 52 53 54

6 0 14 15 16 0 12 0 0 0 0 0 18 0 28 27 26 25 24 0 0 0 0 0 0 31 0 41 40 39 38 37 0 45 46 47 46 45 44 0 56 55 56 57 0 51 52 53 54 55

7 0 13 14 15 0 13 0 0 0 0 0 19 0 0 28 27 26 25 0 0 0 0 0 0 32 0 42 41 40 39 38 0 44 45 46 47 46 45 0 57 56 57 58 0 52 53 54 55 56

8 0 12 13 14 0 14 0 0 0 0 21 20 21 0 0 0 0 26 0 0 0 0 0 34 33 0 0 0 0 0 39 0 43 44 45 46 47 46 0 0 0 0 0 0 53 54 55 56 57

9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58

10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

11 12 13 0 15 16 17 0 0 0 0 22 23 24 0 0 0 0 29 0 0 0 0 0 35 36 0 0 0 0 0 42 0 0 0 0 0 0 49 0 0 0 0 0 0 56 57 58 59 60

12 13 0 0 0 17 18 0 0 0 0 0 24 0 0 33 32 31 30 0 0 0 0 0 0 37 0 47 46 45 44 43 0 55 54 53 52 51 50 0 66 65 64 63 0 57 58 59 60 61

13 14 0 0 0 18 19 0 0 0 0 0 25 0 35 34 33 32 31 0 0 0 0 0 0 38 0 48 47 46 45 44 0 56 55 54 53 52 51 0 65 64 63 62 0 58 59 60 61 62

14 0 0 0 0 0 20 0 0 0 0 0 26 0 36 35 34 33 32 0 0 0 0 0 0 39 0 0 0 0 0 45 0 0 0 0 0 53 52 0 64 63 62 61 60 59 60 61 62 63

15 0 0 0 0 0 21 0 0 0 0 28 27 0 37 36 35 34 33 0 0 0 0 0 0 40 0 50 49 48 47 46 0 56 57 56 55 54 53 0 65 64 0 0 0 60 61 62 63 64

16 0 24 25 26 0 22 0 0 0 0 0 28 0 38 37 36 35 34 0 0 0 0 0 0 41 0 51 50 49 48 47 0 55 56 57 56 55 54 0 66 65 66 67 0 61 62 63 64 65

17 0 23 24 25 0 23 0 0 0 0 0 29 0 0 38 37 36 35 0 0 0 0 0 0 42 0 52 51 50 49 48 0 54 55 56 57 56 55 0 67 66 67 68 0 62 63 64 65 66

18 0 22 23 24 0 24 0 0 0 0 31 30 31 0 0 0 0 36 0 0 0 0 0 44 43 0 0 0 0 0 49 0 53 54 55 56 57 56 0 0 0 0 0 0 63 64 65 66 67

19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68

20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69

21 22 23 0 25 26 27 0 0 0 0 32 33 34 0 0 0 0 39 0 0 0 0 0 45 46 0 0 0 0 0 52 0 0 0 0 0 0 59 0 0 0 0 0 0 66 67 68 69 70

22 23 0 0 0 27 28 0 0 0 0 0 34 0 0 43 42 41 40 0 0 0 0 0 0 47 0 57 56 55 54 53 0 65 64 63 62 61 60 0 76 75 74 73 0 67 68 69 70 71

23 24 0 0 0 28 29 0 0 0 0 0 35 0 45 44 43 42 41 0 0 0 0 0 0 48 0 58 57 56 55 54 0 66 65 64 63 62 61 0 75 74 73 72 0 68 69 70 71 72

24 0 0 0 0 0 30 0 0 0 0 0 36 0 46 45 44 43 42 0 0 0 0 0 0 49 0 0 0 0 0 55 0 0 0 0 0 63 62 0 74 73 72 71 70 69 70 71 72 73

25 0 0 0 0 0 31 0 0 0 0 38 37 0 47 46 45 44 43 0 0 0 0 0 0 50 0 60 59 58 57 56 0 66 67 66 65 64 63 0 75 74 0 0 0 70 71 72 73 74

26 0 34 35 36 0 32 0 0 0 0 0 38 0 48 47 46 45 44 0 0 0 0 0 0 51 0 61 60 59 58 57 0 65 66 67 66 65 64 0 76 75 76 77 0 71 72 73 74 75

27 0 33 34 35 0 33 0 0 0 0 0 39 0 0 48 47 46 45 0 0 0 0 0 0 52 0 62 61 60 59 58 0 64 65 66 67 66 65 0 77 76 77 78 0 72 73 74 75 76

28 0 32 33 34 0 34 0 0 0 0 41 40 41 0 0 0 0 46 0 0 0 0 0 54 53 0 0 0 0 0 59 0 63 64 65 66 67 66 0 0 0 0 0 0 73 74 75 76 77

29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78

30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79

31 32 33 0 35 36 37 0 0 0 0 42 43 44 0 0 0 0 49 0 0 0 0 0 55 56 0 0 0 0 0 62 0 0 0 0 0 0 69 0 0 0 0 0 0 76 77 78 79 80

32 33 0 0 0 37 38 0 0 0 0 0 44 0 0 53 52 51 50 0 0 0 0 0 0 57 0 67 66 65 64 63 0 75 74 73 72 71 70 0 86 85 84 83 0 77 78 79 80 81

33 34 0 0 0 38 39 0 0 0 0 0 45 0 55 54 53 52 51 0 0 0 0 0 0 58 0 68 67 66 65 64 0 76 75 74 73 72 71 0 85 84 83 82 0 78 79 80 81 82

34 0 0 0 0 0 40 0 0 0 0 0 46 0 56 55 54 53 52 0 0 0 0 0 0 59 0 0 0 0 0 65 0 0 0 0 0 73 72 0 84 83 82 81 80 79 80 81 82 83

35 0 0 0 0 0 41 0 0 0 0 48 47 0 57 56 55 54 53 0 0 0 0 0 0 60 0 70 69 68 67 66 0 76 77 76 75 74 73 0 85 84 0 0 0 80 81 82 83 84

36 0 44 45 46 0 42 0 0 0 0 0 48 0 58 57 56 55 54 0 0 0 0 0 0 61 0 71 70 69 68 67 0 75 76 77 76 75 74 0 86 85 86 87 0 81 82 83 84 85

37 0 43 44 45 0 43 0 0 0 0 0 49 0 0 58 57 56 55 0 0 0 0 0 0 62 0 72 71 70 69 68 0 74 75 76 77 76 75 0 87 86 87 88 0 82 83 84 85 86

38 0 42 43 44 0 44 0 0 0 0 51 50 51 0 0 0 0 56 0 0 0 0 0 64 63 0 0 0 0 0 69 0 73 74 75 76 77 76 0 0 0 0 0 0 83 84 85 86 87

39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88

40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89

41 42 43 0 45 46 47 0 0 0 0 52 53 54 0 0 0 0 59 0 0 0 0 0 65 66 0 0 0 0 0 72 0 0 0 0 0 0 79 0 0 0 0 0 0 86 87 88 89 90

42 43 0 0 0 47 48 0 0 0 0 0 54 0 0 63 62 61 60 0 0 0 0 0 0 67 0 77 76 75 74 73 0 85 84 83 82 81 80 0 96 95 94 93 0 87 88 89 90 91

43 44 0 0 0 48 49 0 0 0 0 0 55 0 65 64 63 62 61 0 0 0 0 0 0 68 0 78 77 76 75 74 0 86 85 84 83 82 81 0 95 94 93 92 0 88 89 90 91 92

44 0 0 0 0 0 50 0 0 0 0 0 56 0 66 65 64 63 62 0 0 0 0 0 0 69 0 0 0 0 0 75 0 0 0 0 0 83 82 0 94 93 92 91 90 89 90 91 92 93

45 0 0 0 0 0 51 0 0 0 0 58 57 0 67 66 65 64 63 0 0 0 0 0 0 70 0 80 79 78 77 76 0 86 87 86 85 84 83 0 95 94 0 0 0 90 91 92 93 94

46 0 54 55 56 0 52 0 0 0 0 0 58 0 68 67 66 65 64 0 0 0 0 0 0 71 0 81 80 79 78 77 0 85 86 87 86 85 84 0 96 95 96 97 0 91 92 93 94 95

47 0 53 54 55 0 53 0 0 0 0 0 59 0 0 68 67 66 65 0 0 0 0 0 0 72 0 82 81 80 79 78 0 84 85 86 87 86 85 0 97 96 97 98 0 92 93 94 95 96

48 0 52 53 54 0 54 0 0 0 0 61 60 61 0 0 0 0 66 0 0 0 0 0 74 73 0 0 0 0 0 79 0 83 84 85 86 87 86 0 0 0 0 0 0 93 94 95 96 97

49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98

1696

■参照サイト
AtCoder Beginner Contest 088

C++の練習を兼ねて, AtCoder Beginner Contest 088 の 問題D (D – Grid Repainting) を解いてみた.

コメントを残す コメントをキャンセル

C++の練習を兼ねて, AtCoder Beginner Contest 088 の問題D (D – Grid Repainting) を解いてみた.

コメントを残すコメントをキャンセル