USACO-Section 2.4 The Tamworth Two(シミュレーション)

2857 ワード

説明
2匹の牛が森に逃げた.農夫のジョンは彼の専門家の技術でこの2頭の牛を追跡し始めた.あなたの任務は彼らの行為(牛とジョン)をシミュレートすることです.
追撃は10 x 10の平面メッシュ内で行われる.1つの格子は次のようになります.
一つの障害物、2頭の牛(いつも一緒にいる)、あるいは農民ジョン.
2頭の牛と農民のジョンは同じ格子内にいることができますが(彼らが出会ったとき)、障害のある格子に入ることはできません.
1つの格子は次のようになります.
.    
*     
C     
F   John 

ここに地図の例があります.
*...*.....
......*...
...*...*..
..........
...*.F....
*.....*...
...*......
..C......*
...*.*....
.*.*......


牛は地図の中で固定的な方法でぶらぶらしている.毎分、前に移動したり曲がったりすることができます.前方に障害がなければ(地図の端も障害です)、元の方向に進みます.そうでなければ、この1分で時計回りに90度回転します.同時に、地図から離れません.
農民のジョンは牛の移動方法をよく知っていて、彼もこのように移動しています.
毎回(毎分)農民のジョンと2頭の牛の移動は同時です.もし彼らが移動している間に相手を通り抜けたが、同じ格で出会っていなければ、私たちは彼らが出会ったとは思わない.彼らがある分の末にある格子で出会ったとき、追跡は終わった.
農夫のジョン、2頭の牛、すべての障害の位置を示す地図を10行読みました.各行には10文字しか含まれていません.意味は上記と同じです.地図には「F」と「C」しかありません.F′とC′は最初は同じ格子には入らなかった.
農夫のジョンが牛を捕まえるのに何分かかるかを計算し、牛と農夫のジョンの最初の行動方向が真北(上)であると仮定します.ジョンと牛が永遠に出会わなければ、0を出力します.
書式設定
PROGRAM NAME: ttwo
INPUT FORMAT:
(file ttwo.in)
1~10行目:
行ごとに10文字で、上記のような地図を表します.
OUTPUT FORMAT:
(file ttwo.out)
ジョンが牛たちを捕まえるのにどれだけの時間がかかるかを示す数字を出力します.ジョンが牛を捕まえられない場合は0を出力します.
SAMPLE INPUT
*...*.....
......*...
...*...*..
..........
...*.F....
*.....*...
...*......
..C......*
...*.*....
.*.*......

SAMPLE OUTPUT
49

水問題、シミュレーションすればいい
地図が小さいため、全部で10*10*4種類の状態があり、牛と人は160,000種類の状態があり、160,000分を超えてもまだ出会っていない場合は、必ず2つの状態が繰り返され、つまり循環に陥り、出会うことはありません.
/*
ID: your_id_here
PROG: ttwo
LANG: C++
*/
#include <cstdio>
#include <cstring>

using namespace std;

int i,j,px,py,pd,cx,cy,cd;
char mp[15][15];

void mov(int& x,int& y,int& d) {
    switch(d) {
    case 0:
        if(mp[x-1][y]=='*')
            d=1;
        else
            --x;
        break;
    case 1:
        if(mp[x][y+1]=='*')
            d=2;
        else
            ++y;
        break;
    case 2:
        if(mp[x+1][y]=='*')
            d=3;
        else
            ++x;
        break;
    case 3:
        if(mp[x][y-1]=='*')
            d=0;
        else
            --y;
    }
}

int main() {
    freopen("ttwo.in","r",stdin);
    freopen("ttwo.out","w",stdout);
    for(i=1;i<=10;++i) {
        scanf("%s",mp[i]+1);
        for(j=1;j<=10;++j)
            if(mp[i][j]=='C')
                cx=i,cy=j;
            else if(mp[i][j]=='F')
                px=i,py=j;
    }
    pd=cd=0;
    for(i=0;i<=11;++i)//        ,    
        mp[i][0]=mp[0][i]=mp[11][i]=mp[i][11]='*';
    for(i=0;i<160000;++i) {
        if(px==cx&&py==cy)
            break;
        mov(px,py,pd);
        mov(cx,cy,cd);
    }
    printf("%d
",i<=160000?i:0); return 0; }