JOI予選Eのチーズ (Cheese)を解説

メモです。

競プロ初心者ですが、けんちょんさんのBFSの記事
を読んで、早速BFSの問題を解きたいと思いました。
JOIの過去問から調べると、チーズと言う問題がBFSで解けるそうなのでやって見ました。
初心者なりにポイントだなと思ったことを述べていきます。

第１０回日本情報オリンピック 予選問題
E - チーズ (Cheese)を解いていきます。

E - チーズ (Cheese)

問題
今年も JOI 町のチーズ工場がチーズの生産を始め，ねずみが巣から顔を出した．JOI 町は東西南北に区画整理されていて，各区画は巣，チーズ工場，障害物，空き地のいずれかである．ねずみは巣から出発して全てのチーズ工場を訪れチーズを
1
個ずつ食べる．
この町には，
N
個のチーズ工場があり，どの工場も
１
種類のチーズだけを生産している．チーズの硬さは工場によって異なっており，硬さ
1
から
N
までのチーズを生産するチーズ工場がちょうど
1
つずつある．
ねずみの最初の体力は
1
であり，チーズを
1
個食べるごとに体力が
1
増える．ただし，ねずみは自分の体力よりも硬いチーズを 食べることはできない．
ねずみは，東西南北に隣り合う区画に
1
分で移動することができるが，障害物の区画には入ることができない．チーズ工場をチーズを食べずに通り過ぎる こともできる．すべてのチーズを食べ終えるまでにかかる最短時間を求めるプログラ ムを書け．ただし，ねずみがチーズを食べるのにかかる時間は無視できる．

区間を移動するごとに、1分で移動できるので、区間の移動距離が少ないものを求めればいいですね。つまり最短経路の問題であると言えます。（と、本番では考えて、BFSを使おうとするべきだなぁ）

どこでBFSを使おうか

もちろん、スタートしてからチーズを食べ終わるまでの最短。
だけど体力があるから、食べれるチーズが限られるなぁ。

と言っても、最初は1のチーズしか食べられないし、次は2のチーズしか食べられない。そっか、つまり、1から順番に回っていけばいいのか。

そして、分けたほうがやりやすそう。スタートから1の最短、1から2の最短...と言う風にBFSを順番に使っていく。

BFSを実装

私は区間をvector<string>に入れた。

S..
...
..1

の場合

vector<string> mp = {"S..","...","..1"};

と保存されているmp[x][y]でアクセスできるため、グラフの頂点の位置を表すのは(x,y)

二つの値のペアなので

pair<int,int>が使いやすい。

必要な状態

与えられた、H,W,Nそして各区間以外に必要な状態は何だろうか。

• BFSなので、訪問済みかどうかを表す二次元配列
• BFSなので、キュー
• BFSスタート時点の(x,y)

キューの頂点に必要な状態は？

• スタート時点からの距離（時間）
• 位置(x,y)

キューの頂点の状態を持たせるとき、
構造体を作ると良い（良いかは知らないけど好き）。

struct P {
    pair<int, int> pos;
    int cost;
};

posが座標、costが距離（時間）です。

訪問する頂点での操作

• 訪問済みだったら何もしない
• そうでなかったら、訪問済みにしておく
• もし、食べれるチーズがある頂点ならBFS終わらせる
• お隣（上、下、右、左）をのぞいて存在していて、障害物でなければ、キューに追加しておく

うん、BFSですね。

コード
細かいところ気にしてないです。
でも細かいところ気になった方は遠慮なくコメントやTwitterでリプください。

# include <iostream>
# include <string>
# include <vector>
# include <map>

# include <algorithm>
# include <queue>
# include <cctype>

using namespace std;

# define rep(i, n) for (int i = 0; i < n; i++)

int h, w, n, ans;
pair<int,int> start;
vector<string> mp;
pair<int,int> move_pos[4] = {{0,1},{1,0},{0,-1},{-1,0}};

struct P {
    pair<int, int> pos;
    int cost;
};

P BFS(char goal, int x, int y) {
    queue<P> que;
    bool seens[1003][1003] = {};
    que.push({{x,y},0});

    while(!que.empty()) {
        P v = que.front();
        que.pop();
    
        pair<int, int> now = v.pos;

        if(seens[now.first][now.second]) continue;
        seens[now.first][now.second] = true;

        if ( mp[now.first][now.second] == goal) {
            return v;
        }
        rep(i,4) {
            pair<int,int> next;
            next.first = now.first + move_pos[i].first;
            next.second = now.second + move_pos[i].second;
            if (next.first >=0 && next.first <h
                && next.second >=0 && next.second < w
                && mp[next.first][next.second] != 'X'
                ) {
                    que.push({{next.first,next.second}, v.cost + 1});
                }
        }
    }
    return {{x,y},0};
}

int main() {
    cin >> h >> w >> n;
    rep(i, h) {
        string line;
        cin >> line;
        mp.push_back(line);
        rep(k, w) {
            if (line[k] == 'S') {
                start = {i,k};
            }
        }
    }

    rep(i, n) {
        P result = BFS('0' + (i + 1), start.first, start.second);
        start = result.pos;
        ans = ans + result.cost;
    }
 
    cout << ans << '\n';
}

　注意点

'0' + iってやったら、charの数字になりますよねー
変なのー
C++あんま書かないので、こうなるかなぁとかゆるゆるにかくとあとでバグの元なので、一つ一つちゃんと確実に書いていきたい。（抽象的すぎて意味わからん）

まとめ

一問で得られたことはとても多い。
”やるだけ”問題を解くより、こう言うよく使われるアルゴリズムの問題を解いていろんな問題に対応できるようになろうと思った。
今日は競プロにのめり込んでしまった。楽しくなってきたかもしれない。
でも時間が溶けすぎて他のこととどう両立させるんだ？！
もっとDP極めるぞ、蟻本熟読するぞ。