Namaran

Code daily. Without assist.

2026-09-01

walls.c

int fewest_walls(int h, int w, const char* grid[]) {
}

grid は h 行 w 列の盤面で、grid[r][c] は '.' か '#' です。左上のマスから右下のマスまで、上下左右に隣り合うマスへ1つずつ進むとき、入った '#' のマスの個数の最小値を返す fewest_walls を書いてください。左上のマスは必ず '.' で、右下のマスが '#' ならそれも数えます。盤面が1行1列なら0を返します。

入力例 1

fewest_walls(3, 4, (const char*[]){".#..", ".##.", "...#"})

出力例 1

1

入力例 2

fewest_walls(3, 3, (const char*[]){".##", "###", "##."})

出力例 2

3

入力例 3

fewest_walls(1, 1, (const char*[]){"."})

出力例 3

0
Reference
int fewest_walls(int h, int w, const char* grid[]) {
    int dist[h * w], dq[4 * h * w], head = 2 * h * w, tail = head;
    for (int i = 0; i < h * w; i++) {
        dist[i] = h * w;
    }
    dist[0] = 0;
    dq[tail++] = 0;
    static const int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
    while (head < tail) {
        int v = dq[head++], r = v / w, c = v % w;
        for (int k = 0; k < 4; k++) {
            int nr = r + dr[k], nc = c + dc[k];
            if (nr < 0 || nr >= h || nc < 0 || nc >= w) {
                continue;
            }
            int u = nr * w + nc, cost = grid[nr][nc] == '#';
            if (dist[v] + cost < dist[u]) {
                dist[u] = dist[v] + cost;
                if (cost == 0) {
                    dq[--head] = u;
                } else {
                    dq[tail++] = u;
                }
            }
        }
    }
    return dist[h * w - 1];
}

隣のマスへ進む費用を、行き先が '.' なら0、'#' なら1と決めると、答えは左上から右下までの費用の合計の最小値です。dist[r * w + c] にそのマスまでの最小の費用の候補を持ち、費用0の移動で小さくなったマスは dq の先頭に、費用1の移動で小さくなったマスは末尾に入れます。先頭に入るマスは取り出したばかりのマスと同じ費用なので、dq の中の費用はいつも小さい順に並び、右下の dist は最小値になります。費用が0と1の2種類しかないときに使えるこの方法は、0-1 BFS と呼ばれます。

ふつうの幅優先探索の癖で、マスを初めて見つけた時点で費用を確定させると間違えます。費用1の移動で先に見つかったマスに、あとから費用0で着く道が見つかることがあるからです。そのため dist[v] + cost < dist[u] で比べ、費用が下がったときは同じマスをもう一度キューに入れます。1つのマスが入るのは多くても2回なので、dq には先頭側と末尾側に 2 * h * w 個ずつ場所を取り、head を真ん中から始めています。

掲載したのは参考実装で、唯一の正解ではありません。優先度付きキューを使うダイクストラ法(Dijkstra's algorithm)でも同じ答えが出ます。両端キューで済むのは、費用が0と1だけで、取り出す順を先頭か末尾かの2択で保てるからです。