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

C++の練習を兼ねて, 第三回アルゴリズム実技検定の問題G (グリッド金移動) を解いてみた.

■感想.
1. 問題Gは, 方針を絞り込むことが出来たので, AC版に到達できたと思う.
2. 過去問(第九回アルゴリズム実技検定 F – 将棋のように) に似ている問題に見えたため, 実装を一部流用している.
3. 幅優先探索(応用版, 移動可能方向の構築)の復習が出来たので, 非常に良かったと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
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
const int D1 = 505;
const int D2 = 250;
int board[(D1 + 1) * (D1 + 1)];

int main(){
    
    // 1. 入力情報.
    int N, X, Y;
    scanf("%d %d %d", &N, &X, &Y);
    X += D2;
    Y += D2;
    rep(i, N){
        int x, y;
        scanf("%d %d", &x, &y);
        x += D2;
        y += D2;
        board[D1 * x + y] = 1;
    }
    
    // 2. 移動可能な方向は？
    // 過去問参照(第九回 アルゴリズム実技検定 F - 将棋のように)
    // https://atcoder.jp/contests/past202112-open/tasks/past202112_f
    vp dir;
    dir.pb({1, 1});
    dir.pb({0, 1});
    dir.pb({-1, 1});
    dir.pb({1, 0});
    dir.pb({-1, 0});
    dir.pb({0, -1});
    
    // 3. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](int s, int H, int W, int* d) -> void{
        // 空のキュー.
        queue<int> q;
        
        // 訪問済みフラグ設定.
        d[s] = 0;
        
        // 探索地点 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 || board[n]) continue;
                
                // 移動先のマスで, 訪問可能 かつ 未訪問 であれば, 最短距離を設定.
                if(d[n] == -1) d[n] = d[v] + 1, q.push(n);
            }
        }
    };
    int d[D1 * D1];
    rep(i, D1 * D1) d[i] = -1;
    bfs(D1 * D2 + D2, D1, D1, d);
    
    // 4. 出力.
    printf("%d\n", d[D1 * X + Y]);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

const int D1 = 505;

const int D2 = 250;

int board[(D1 + 1) * (D1 + 1)];

int main(){

// 1. 入力情報.

int N, X, Y;

scanf("%d %d %d", &N, &X, &Y);

X += D2;

Y += D2;

rep(i, N){

int x, y;

scanf("%d %d", &x, &y);

x += D2;

y += D2;

board[D1 * x + y] = 1;

}

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

// 過去問参照(第九回アルゴリズム実技検定 F - 将棋のように)

// https://atcoder.jp/contests/past202112-open/tasks/past202112_f

vp dir;

dir.pb({1, 1});

dir.pb({0, 1});

dir.pb({-1, 1});

dir.pb({1, 0});

dir.pb({-1, 0});

dir.pb({0, -1});

// 3. bfs.

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

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

// 空のキュー.

queue<int> q;

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

d[s] = 0;

// 探索地点 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 || board[n]) continue;

// 移動先のマスで, 訪問可能かつ未訪問であれば, 最短距離を設定.

if(d[n] == -1) d[n] = d[v] + 1, q.push(n);

}

};

int d[D1 * D1];

rep(i, D1 * D1) d[i] = -1;

bfs(D1 * D2 + D2, D1, D1, d);

// 4. 出力.

printf("%d\n", d[D1 * X + Y]);

return 0;

}

[入力例]
1 2 2
1 1

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

[入力例]
1 2 2
2 1

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

[入力例]
5 -2 3
1 1
-1 1
0 1
-2 1
-3 1

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

[入力例]
7 4 4
4 1
4 3
1 1
1 5
2 1
2 2
3 3

[出力例]
5

[入力例]
22 10 3
3 1
6 1
8 1
2 2
3 2
7 2
9 2
2 3
5 3
6 3
7 3
9 3
4 4
7 4
9 4
1 5
3 5
7 5
10 5
6 6
8 6
6 7

[出力例]
11

[入力例]

1 2 2

1 1

[出力例]

※AtCoderテストケースより

[入力例]

1 2 2

2 1

[出力例]

※AtCoderテストケースより

[入力例]

5 -2 3

1 1

-1 1

0 1

-2 1

-3 1

[出力例]

※AtCoderテストケースより

[入力例]

7 4 4

4 1

4 3

1 1

1 5

2 1

2 2

3 3

[出力例]

[入力例]

22 10 3

3 1

6 1

8 1

2 2

3 2

7 2

9 2

2 3

5 3

6 3

7 3

9 3

4 4

7 4

9 4

1 5

3 5

7 5

10 5

6 6

8 6

6 7

[出力例]

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

C++の練習を兼ねて, 第三回 アルゴリズム実技検定 の 問題G (グリッド金移動) を解いてみた.

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

C++の練習を兼ねて, 第三回アルゴリズム実技検定の問題G (グリッド金移動) を解いてみた.

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