PKU 1024 Tester Program

Tester Program

一意な最短経路が存在する場合に経路を返す関数を作る。出力をそのまま関数に与えて入力と同じ経路が返ってきて、なおかつどの壁を消去しても入力と異なる経路が返ってくれば正しい答えである。最短経路が一意かどうかの判定は幅優先探索中に複数の方向から同じ時間で到達したマスに印を付けることで行う。最短経路の途中に印の付いたマスがあれば最短経路が複数ある。

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

using namespace std;

struct WALL { int x1, y1, x2, y2; };
typedef vector<WALL>::iterator witer;

string solve( int W, int H, vector<WALL> wall, int gx, int gy );

int main()
{
    int t;  cin >> t;
    while ( t-- > 0 )
    {
        //  読み込み
        int W, H, M;
        string path;
        cin >> W >> H >> path >> M;

        vector<WALL> wall(M);
        for ( int i=0; i<M; i++ )
            cin >> wall[i].x1 >> wall[i].y1 >> wall[i].x2 >> wall[i].y2;

        //  ゴール位置を求める
        int gx = 0,  gy = 0;
        for ( int i=0; i<(int)path.size(); i++ )
        switch ( path[i] )
        {
            case 'U':  gy++;  break;
            case 'D':  gy--;  break;
            case 'L':  gx--;  break;
            case 'R':  gx++;  break;
        }

        //  一意な最短経路であることと
        //  余分な壁がないことをチェック
        bool correct = path == solve( W, H, wall, gx, gy );

        if ( correct )
        for ( int i=0; i<(int)wall.size(); i++ )
        {
            vector<WALL> temp = wall;
            temp.erase( temp.begin() + i );

            if ( path == solve( W, H, temp, gx, gy ) )
                correct = false;
        }
        
        cout << ( correct ? "CORRECT" : "INCORRECT" ) << endl;
    }

    return 0;
}

//  一意の最短経路があれば最短経路返す
//  無ければ空文字列を返す
struct CELL
{
    int     time;   //  最短到達時刻
    char    dir;    //  最後に移動した方向
    bool    multi;  //  複数経路があるか

    CELL() : time(INT_MAX), multi(false) {}
};

string solve( int W, int H, vector<WALL> wall, int gx, int gy )
{
    vector<vector<CELL> > maze( W, vector<CELL>( H ) );

    char dc[] = { 'U', 'D', 'L', 'R' };
    int  dx[] = {   0,   0,  -1,   1 };
    int  dy[] = {   1,  -1,   0,   0 };

    //  幅優先探索で最短経路を求める
    maze[0][0].time = 0;

    for ( int t=0; maze[gx][gy].time==INT_MAX; t++ )
    {
        for ( int x=0; x<W; x++ )
        for ( int y=0; y<H; y++ )
        if ( maze[x][y].time == t )
        {
            for ( int d=0; d<4; d++ )
            {
                //  移動先
                int tx = x + dx[d];
                int ty = y + dy[d];

                //  壁に遮られていないか
                bool f = true;

                for ( witer w=wall.begin(); w!=wall.end(); w++ )
                    if ( w->x1 == x  &&  w->y1 == y  &&
                         w->x2 == tx  &&  w->y2 == ty  ||
                         w->x1 == tx  &&  w->y1 == ty  &&
                         w->x2 == x  &&  w->y2 == y )
                        f = false;

                if ( f  &&
                     0 <= tx  &&  tx < W  &&  0 <= ty  &&  ty < H )
                {
                    if ( maze[tx][ty].time == t+1 )
                        maze[tx][ty].multi = true;
                    if ( maze[tx][ty].time > t + 1 )
                        maze[tx][ty].time = t + 1,
                        maze[tx][ty].dir = dc[d];
                }
            }
        }
    }

    //  最短経路
    string path;
    bool success = true;

    int x = gx;
    int y = gy;

    while ( x != 0  ||  y != 0 )
    {
        if ( maze[x][y].multi )
            success = false;

        path = maze[x][y].dir + path;

        switch ( maze[x][y].dir )
        {
            case 'U':  y--;  break;
            case 'D':  y++;  break;
            case 'L':  x++;  break;
            case 'R':  x--;  break;
        }
    }

    return success ? path : "";
}