2010年予選第8問(AOJ:No.0223)

C++

3日ぶりの更新。部活で演奏会のリハーサルや本番で忙しかったですが、

無事成功しました。



パソコン甲子園昨年の過去問「迷子の双子」です。

問題文・入力例等は、AOJにあるので下のURLからどうぞ。



http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0223



また、パソコン甲子園公式から過去問とその解説をPDFで見ることもできます。



http://web-ext.u-aizu.ac.jp/pc-concours/2011/03/03_kakomon.html



では、続きからどうぞ。



#include <iostream>

#include <queue>

#include <map>

#define INF        (1<<21)

using namespace std;
typedef pair<int, int> Point;

typedef pair<point, point> PSet;
const int vx[4] = { 1, -1, 0, 0 }, vy[4] = { 0, 0, 1, -1 };

int X, Y;

int maze[50][50];

Point T, K;
bool isBlock( Point t ) {

        int x = t.first, y = t.second;

        if( x < 0 || X <= x || y < 0 || Y <= y ) return true;

        return maze[y][x];

}
int bfs() {

        queue<pset> Q;

        map<pset, int> Time;

        map<pset, bool> M;
        PSet p, q;

        p.first = T; p.second = K;

        Q.push( p );

        Time[p] = 0;

        M[p] = true;

        

        while( !Q.empty() ) {

                p = Q.front(); Q.pop();

                int tx = p.first.first, ty = p.first.second, kx = p.second.first, ky = p.second.second;

                if( tx == kx && ty == ky ) return Time[p];

                if( Time[p] >= 100 ) break;

                

                for( int i = 0; i < 4; i++ ) {

                        q.first = Point( tx + vx[i], ty + vy[i] );

                        q.second = Point( kx - vx[i], ky - vy[i] );

                        if( isBlock( q.first ) ) q.first = Point( tx, ty );

                        if( isBlock( q.second ) ) q.second = Point( kx, ky );

                        if( !M[q] ) {

                                Q.push( q );

                                M[q] = true;

                                Time[q] = Time[p] + 1;

                        }

                }

        }

        

        return INF;

}
main() {

        while( cin >> X >> Y && X && Y ) {

                int tx, ty, kx, ky;

                cin >> tx >> ty >> kx >> ky;

                T.first = tx - 1; T.second = ty - 1;

                K.first = kx - 1; K.second = ky - 1;

                

                for( int i = 0; i < Y; i++ )

                        for( int j = 0; j < X; j++ ) cin >> maze[i][j];

                

                int time = bfs();

                if( time != INF ) cout << time << endl;

                else cout << "NA" << endl;

        }

}



今回は時間は計ってないけど、30分以上かかった気がする。

去年参加したときは、本番で幅優先探索も知らずに無謀に挑んでたなあ。

本当に、去年はエラトステネスくらいしか知らないレベルで挑んでいたので

今から考えると時間の無駄だった…



本問は最短時間を求めよとのことなので、幅優先探索で行きましょう。

深さ優先探索はすべてのパターンを試して探索するときに使いますが、

今回は最短のパターンが見つかったらすぐに探索を終了するのでこちらがよいです。



ちなみに、ここまで時間がかかったのは、問題文をちゃんと読んでいなかったから…

時間が100以上かかる時はNAを出力せよと書いてあるのに、

読んでおらず実装していなかった(ソースの36行目)ので、

AOJに2、3回提出してもWAを渡されてまったく原因がわかりませんでしたｗ

まあ、問題文はちゃんと読めっていう教訓になったのでいいかな。



あと、実際はpairを使わずに、公式の解説のように座標を現在時間とまとめたクラスを作って

キューにぶち込んだ方が速度的には早い気がする…。

このソースでは1250ミリ秒かかってるそうです。

AOJでは制限時間5秒なので問題はなかったですが。