題目來(lái)自 USACO
題目翻譯見 NOCOW

思路

題目很軟萌，看懂規(guī)則模擬就好了。可能是我代碼能力下降太快了，寫了好久都覺得丑得發(fā)嗔，一點(diǎn)都不萌。

第一版 AC 代碼

/*
ID: 
LANG: C++
TASK: ttwo
*/

#include <cstdio>
#include <cstdlib>
#define valid(x) ((x) >= 0 && (x) <= 9)

enum dir {N, E, S, W};
char map[10][10];
int x[2], y[2]; //(x[1], y[1])farmer, (x[0], y[0])cow
dir dirs[2] = {N, N}; //[1]farmer, [0]cow

void updateMap(int xNext, int yNext, int obj){
    if(!valid(xNext) || !valid(yNext) || map[xNext][yNext] == '*'){
        dirs[obj] = dir((dirs[obj] + 1) % 4);
    }else{
        map[xNext][yNext] = map[x[obj]][y[obj]];
        map[x[obj]][y[obj]] = '.';
        x[obj] = xNext;
        y[obj] = yNext;
    }
}

void move(int obj){
    switch(dirs[obj]){
        case N: updateMap(x[obj] - 1, y[obj], obj); break;
        case E: updateMap(x[obj], y[obj] + 1, obj); break;
        case S: updateMap(x[obj] + 1, y[obj], obj); break;
        case W: updateMap(x[obj], y[obj] - 1, obj); break;
    }
}

int main(){
    FILE *fin = fopen("ttwo.in", "r");
    FILE *fout = fopen("ttwo.out", "w");

    for(int i = 0; i < 10; i ++){
        fscanf(fin, "%s", &(map[i]));
    }

    for(int i = 0; i < 10; i ++){
        for(int j = 0; j < 10; j ++){
            if(map[i][j] == 'F') x[1] = i, y[1] = j;
            if(map[i][j] == 'C') x[0] = i, y[0] = j;
        }
    }

    int steps = 1;
    for(; steps < 100000; steps ++) {
        move(0);
        move(1);
        if(x[0] == x[1] && y[0] == y[1]) break;
    }
    if(steps == (100000)) steps = 0;
    fprintf(fout, "%d\n", steps);

    return 0;
}

結(jié)果：

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.000 secs, 4180 KB]
   Test 2: TEST OK [0.000 secs, 4180 KB]
   Test 3: TEST OK [0.000 secs, 4180 KB]
   Test 4: TEST OK [0.000 secs, 4180 KB]
   Test 5: TEST OK [0.000 secs, 4180 KB]
   Test 6: TEST OK [0.000 secs, 4180 KB]
   Test 7: TEST OK [0.000 secs, 4180 KB]
   Test 8: TEST OK [0.000 secs, 4180 KB]
   Test 9: TEST OK [0.000 secs, 4180 KB]

All tests OK.

循環(huán)次數(shù)

其中這個(gè)循環(huán)的最大次數(shù) 100000 是我猜的，應(yīng)該 160000 靠譜一些。由于圖中只有 100 個(gè)位置， 又每個(gè)位置可能有 4 個(gè)方向，所以 john 和 cow 總共有 400 * 400 種狀態(tài)，循環(huán)這個(gè)次數(shù)就能判斷是不是永遠(yuǎn)追不上了。

修改

我把四個(gè)方向直接用 int，四個(gè)方向的運(yùn)動(dòng)直接用數(shù)組表示，不再寫一堆條件了。只寫一個(gè) move 函數(shù)，狀態(tài)也就是 x、y、dir 就可以描述了，傳這三個(gè)參就夠了。至于
farmer 和 cow，由給什么實(shí)參決定。好看多了~

/*
ID:
LANG: C++
TASK: ttwo
*/

#include <cstdio>
#include <cstdlib>
#define valid(x) ((x) >= 0 && (x) <= 9)

char map[10][10];
int fx, fy, cx, cy;
int fDir, cDir; //0N, 1E, 2S, 3W;
int xMove[4] = {-1, 0, 1, 0};
int yMove[4] = {0, 1, 0, -1}; //四個(gè)方向move對(duì)x y的影響

void move(int &x, int &y, int &dir){
    int xNext = x + xMove[dir];
    int yNext = y + yMove[dir];

    if(!valid(xNext) || !valid(yNext) || map[xNext][yNext] == '*'){
        dir = (dir + 1) % 4;
    }else{
        map[xNext][yNext] = map[x][y];
        map[x][y] = '.';
        x = xNext;
        y = yNext;
    }
}

int main(){
    FILE *fin = fopen("ttwo.in", "r");
    FILE *fout = fopen("ttwo.out", "w");

    for(int i = 0; i < 10; i ++){
        fscanf(fin, "%s", &(map[i]));
    }

    for(int i = 0; i < 10; i ++){
        for(int j = 0; j < 10; j ++){
            if(map[i][j] == 'F') fx = i, fy = j;
            if(map[i][j] == 'C') cx = i, cy = j;
        }
    }

    int steps = 1;
    for(; steps < 160000; steps ++) {
        move(fx, fy, fDir);
        move(cx, cy, cDir);
        if(cx == fx && cy == fy) break;
    }
    if(steps == (160000)) steps = 0;
    fprintf(fout, "%d\n", steps);

    return 0;
}