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

C++の練習を兼ねて, 第九回アルゴリズム実技検定の問題F (将棋のように) を解いてみた.

■感想.
1. 問題Fは, 方針を絞り込めたので, AC版に到達できた.
2. 幅優先探索(応用版, 移動可能方向の構築)の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト第九回アルゴリズム実技検定の各リンクをご覧下さい.

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vs = vector<string>;
using P = pair<int, int>;
using vp = vector<P>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define a first
#define b second
#define pb push_back

int main(){
    
    // 1. 入力情報.
    int A, B;
    scanf("%d %d", &A, &B);
    A--, B--;
    vs info;
    rep(i, 3){
        char c[11];
        scanf("%s", c);
        string s(c);
        info.pb(s);
    }
    
    // 2. 移動可能な方向は？
    vp dir;
    rep(i, 3) rep(j, 3) if(info[i][j] == '#') dir.pb({i - 1, j - 1});
    
    // 3. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](int s, int H, int W, int* d) -> void{
        // 空のキュー.
        queue<int> q;
        
        // 訪問済みフラグ設定.
        d[s] = 1;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int v = q.front();
            q.pop();
            
            // 取り出した要素を処理.
            // x: 列方向, y: 行方向 で考える.
            int nx, ny, n;
            int cx = v % W , cy = v / W;
            for(auto &p : dir){
                // 移動先.
                nx = cx + p.b;
                ny = cy + p.a;
                n = nx + ny * W;
                
                // 訪問不可能なマス であれば, 処理をスキップ.
                if(nx < 0 || nx >= W || ny < 0 || ny >= H) continue;
                
                // 訪問先のマスで, 訪問可能 かつ 未訪問 であれば, 訪問済みフラグ設定.
                if(!d[n]) d[n] = 1, q.push(n);
            }
        }
        return;
    };
    int d[81];
    rep(i, 81) d[i] = 0;
    bfs(A * 9 + B, 9, 9, d);
    
    // 4. 集計.
    int ans = 0;
    rep(i, 81) if(d[i]) ans++;
    
    // 5. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vs = vector<string>;

using P = pair<int, int>;

using vp = vector<P>;

#define repex(i, a, b, c) for(int i = a; i < b; i += c)

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

#define a first

#define b second

#define pb push_back

int main(){

// 1. 入力情報.

int A, B;

scanf("%d %d", &A, &B);

A--, B--;

vs info;

rep(i, 3){

char c[11];

scanf("%s", c);

string s(c);

info.pb(s);

}

// 2. 移動可能な方向は？

vp dir;

rep(i, 3) rep(j, 3) if(info[i][j] == '#') dir.pb({i - 1, j - 1});

// 3. bfs.

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

auto bfs = [&](int s, int H, int W, int* d) -> void{

// 空のキュー.

queue<int> q;

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

d[s] = 1;

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

q.push(s);

while(!q.empty()){

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

int v = q.front();

q.pop();

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

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

int nx, ny, n;

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

for(auto &p : dir){

// 移動先.

nx = cx + p.b;

ny = cy + p.a;

n = nx + ny * W;

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

if(nx < 0 || nx >= W || ny < 0 || ny >= H) continue;

// 訪問先のマスで, 訪問可能かつ未訪問であれば, 訪問済みフラグ設定.

if(!d[n]) d[n] = 1, q.push(n);

}

return;

};

int d[81];

rep(i, 81) d[i] = 0;

bfs(A * 9 + B, 9, 9, d);

// 4. 集計.

int ans = 0;

rep(i, 81) if(d[i]) ans++;

// 5. 出力.

printf("%d\n", ans);

return 0;

}

[入力例]
2 2
###
#..
...

[出力例]
5
※AtCoderのテストケースより

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

[出力例]
81
※AtCoderのテストケースより

[入力例]
9 9
...
...
..#

[出力例]
1
※AtCoderのテストケースより

[入力例]
8 8
...
...
...

[出力例]
1

[入力例]
5 7
.#.
...
...

[出力例]
5

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

[出力例]
9

[入力例]
2 2
#.#
...
#.#

[出力例]
41

[入力例]
2 8
.#.
#.#
.#.

[出力例]
81

[入力例]

2 2

###

#..

...

[出力例]

※AtCoderのテストケースより

[入力例]

5 4

###

#.#

###

[出力例]

※AtCoderのテストケースより

[入力例]

9 9

...

..#

[出力例]

※AtCoderのテストケースより

[入力例]

8 8

...

[出力例]

[入力例]

5 7

.#.

...

[出力例]

[入力例]

3 3

...

#.#

...

[出力例]

[入力例]

2 2

#.#

...

#.#

[出力例]

[入力例]

2 8

.#.

#.#

.#.

[出力例]

■参照サイト
第九回アルゴリズム実技検定

C++の練習を兼ねて, 第九回 アルゴリズム実技検定 の 問題F (将棋のように) を解いてみた.

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

C++の練習を兼ねて, 第九回アルゴリズム実技検定の問題F (将棋のように) を解いてみた.

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