hogecoder

tsutaj 競技プログラミングの記録

AOJ 2320: Infinity Maze

AOJ

なんか自分の解法と違うやり方でやってる人がわりといたため記事にします。

問題概要

問題原文 → Infinity Maze | Aizu Online Judge

H \times W マスからなる迷路がある。迷路は通路と壁からなり、壁のマスには進入できない。

以下のルールに従って迷路上を 1 ステップずつ進んでいく。

  • 今向いている方向に 1 マス進める (通路である) 場合、そのまま進む。
  • 壁や迷路の端であってその方向に進めない場合、進める方向になるまで時計回りに 90 度向き直し続ける (たとえば北を向いていたなら次は東)。進める方向になったら 1 マス進む。 (向き直す動作は 1 ステップにカウントしない)

スタート地点と最初に向いている方向が与えられるので、 L ステップ後にいる場所と向いている方向を出力せよ。

  • 1 \leq H, W \leq 100
  • 1 \leq L \leq 10^{18}

解答

他の解説記事を見ると、循環部を見つけて剰余でやる人が多かったのですが、(慣れれば) もっと楽な方法で解きました。

まず、今いる座標と向いている方向 (以降、「状態」と呼ぶ) がわかっているとき、 1 ステップ進むことで次にどの状態になるかは簡単に求められます。

また、今の状態がわかっているとき、その 2 ステップ先の状態は、まず 1 ステップ進んで次の状態に行き、その状態からさらに 1 ステップ進むことで求められます。

・・・ということで、これはダブリングそのものです。

具体的には、 \mathrm{nxt} [ i ] [ j ] [ d ] [ k ] := 位置 (i, j) にいて向きが d である状態から 2^{k} ステップ進んだ先の状態 というテーブルを作って解けば良いです。

テーブルの構築パートで O(NM \log L)、答えを求めるパートで O(\log L) なので十分高速に動きます。

実装上の注意としては、壁であるマスや、四方が進入不可能なマス (これは本来踏み入ることのないマスなので無視して良い) ではテーブルの計算が不要であるというところです。間違って計算すると永遠に向き直して TLE の可能性があります。

ソースコード

#include <cstdio>
#include <iostream>
#include <string>
using namespace std;
typedef long long int ll;

struct State {
    int x, y, dir;
};

int N, M;
ll L;
char board[110][110];
State nxt[110][110][4][70];
string pat = "NESW";

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

int main() {
    while(cin >> N >> M >> L, N || M || L) {
        int sx, sy, d;
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                cin >> board[i][j];
                if(pat.find(board[i][j]) != string::npos) {
                    sx = i, sy = j, d = pat.find(board[i][j]);
                }
            }
        }

        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                if(board[i][j] == '#') continue;
                for(int k=0; k<4; k++) {
                    int d = k;
                    int cnt_ng = 0;
                    // 四方が進入不可能だったらなにもしないようにする
                    while(cnt_ng < 4) {
                        int nx = i + dx[d], ny = j + dy[d];

                        bool ok = true;
                        if(nx < 0 || nx >= N || ny < 0 || ny >= M) ok = false;
                        if(board[nx][ny] == '#') ok = false;
                        if(ok) {
                            nxt[i][j][k][0] = State{nx, ny, d};
                            break;
                        }
                        else {
                            cnt_ng++;
                            d = (d + 1) % 4;
                        }
                    }
                }
            }
        }

        for(int m=1; m<65; m++) {
            for(int i=0; i<N; i++) {
                for(int j=0; j<M; j++) {
                    for(int k=0; k<4; k++) {
                        State t = nxt[i][j][k][m-1];
                        nxt[i][j][k][m] = nxt[t.x][t.y][t.dir][m-1];
                    }
                }
            }
        }

        State ans{sx, sy, d};
        for(int b=0; b<60; b++) {
            if(L >> b & 1) {
                ans = nxt[ans.x][ans.y][ans.dir][b];
            }
        }
        printf("%d %d %c\n", ans.x+1, ans.y+1, pat[ans.dir]);
    }
    return 0;
}

ダブリング書くの楽しい (小並感)