okayunのプログラミング日記

主に自分の解いた問題やCodinGameなどの解法などを載せていきます。

POJ3000 - Frogger

この記事は以前あったものを色々あって修正したものです

今日から解いた問題をぼちぼち日記に残しておこうと思います(メモみたいなものなので解説ではありません)。

難易度的にはeasyからnormalと言ったところでしょうか… もしご覧になった方で「こうした方が良いのではないか」などの意見がございましたらどんどんおっしゃってください(^^)

今回の問題は学校の課題で解いたFroggerという問題です。

POJ3000 -- Frogger

車道とその両側に縁石があり、手前の縁石のスタート地点から反対側の縁石のゴールに、指定ターン以内にたどり着けるならばその最小ターンを、無理なら文字列を出力するというもの。  

結果は1060K 47MSでACでした(文字列のピリオドを忘れたせいでWA出しまくってました…)。

言語はC++で、アルゴリズム幅優先探索とメモ化を用いました。

注意しないといけないのが、単にメモ化しようとすると、ターン数が最大105もあるので少し工夫をしないといけません。そこで車の動きの周期性に着目します。

車は1ターンごとに右、もしくは左に1移動しますが、m回ターンが経過すると元の位置に戻ってきます。つまり、iターン目とm+iターン目は、車の配置はすべて同じです。これを利用して、現在のターン数をmで割ったものをメモ化に用います。

dp[i][j][k] := ターンk(現在のターン%m)に位置(i, j)にたどり着いた時の現在のターン数 このようにメモ化することでいくらか効率よく探索することができました(もちろんのことkはせいぜいm-1以下)。計算量はO(n*m2)です。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
using namespace std;

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

inline void readInt(int *a) {
    int c; char s[20] = "";
    for(int i = 0; (c = getchar()) != '\n'; ++i) {
        if (c == ' ') break;
        s[i] = c;
    }
    *a = atoi(s);
}

inline void readInt2(int *a, int *b) {
  int c, p = 0; char s[20] = "";
  for(int i = 0; (c = getchar()) != '\n'; i++) {
    if (c == ' ') { *a = atoi(s); strcpy(s, ""); p = i+1; continue; }
    else s[i] = c;
  }
  *b = atoi(s+p);
}


int t, x, n, m, sx, sy, gx, gy, dp[25][55][55];
vector<string> v;
int vx[5] = {0, -1, 0, 1, 0}, vy[5] = {-1, 0, 1, 0, 0};
bool is_search[25][55][55];

void all_rotate() {
    for (int i = 1; i < n+1; ++i) {
        // right
        if (i%2 == n%2) {
            rotate(v[i].rbegin(), v[i].rbegin()+1, v[i].rend());
        // left
        } else {
            rotate(v[i].begin(), v[i].begin()+1, v[i].end());
        }
    }
}

int bfs() {
    int prevstate = -1, ret = INF;
    queue<pair<pair<int, int>, int> > q; // queue<座標, 何回動いたか>
    rep(i,n+2) rep(j,m) rep(k,m) dp[i][j][k] = INF;
    memset(is_search, false, sizeof(is_search));
    q.push(make_pair(make_pair(sx, sy), 0));
    dp[sx][sy][0] = 0;
    is_search[sx][sy][0] = true;

    while (!q.empty()) {
        pair<pair<int, int>, int> p = q.front(); q.pop();
        if (p.first.first == gx && p.first.second == gy) {
            ret = min(ret, dp[gx][gy][p.second % m]);
            continue;
        }
        if (p.second >= x) continue;
        
        if (prevstate != p.second) {
            all_rotate();
            prevstate = p.second;
        }

        rep (i,5) {
            int nx = p.first.first + vx[i], ny = p.first.second + vy[i];

            if (0 <= nx && nx < n+2 && 0 <= ny && ny < m && 
            is_search[nx][ny][(p.second + 1) % m] == false && v[nx][ny] != 'X') {
                q.push(make_pair(make_pair(nx, ny), p.second + 1));
                dp[nx][ny][(p.second + 1) % m] = dp[p.first.first][p.first.second][p.second % m] + 1;
                is_search[nx][ny][(p.second + 1) % m] = true;
            }
        }
    }

    return ret;
}

int main(void) {
    readInt(&t);

    while (t--) {
        readInt(&x);
        readInt2(&n, &m);
        char str[55] = "";
        string s;

        rep(i,n+2) {
            fgets(str, sizeof(str), stdin);
            str[strlen(str)-1] = '\0';
            s = str;
            v.push_back(s);
            if (i == 0) {
                rep(j,m) {
                    if (v[i][j] == 'G') {
                        gx = i; gy = j;
                        break;
                    }
                }
            } else if (i == n+1) {
                rep(j,m) {
                    if (v[i][j] == 'F') {
                        sx = i; sy = j;
                        break;
                    }
                }
            }
        }

        int ans = bfs();
        
        if (ans != INF) printf("The minimum number of turns is %d.\n", ans);
        else puts("The problem has no solution.");

        v.clear();
    }

    return 0;
}

私が用いた解法の他には、このdp[i][j][k]のkの部分を0と1のみとし、現在と次の状態だけ見るようにした解法(合ってるか不安)や、ダイクストラを拡張したもの、A探索を用いたものなどがありました(Aはとても速かった)。  

とまあこんな感じでしょうか…

説明おかしいぞ!などのご意見ありましたらTwitterまでお願いします。

(というか見る人いるのかな…)