PROB: ttwo

题目来自 USACO
题目翻译见 NOCOW

思路

题目很软萌，看懂规则模拟就好了。可能是我代码能力下降太快了，写了好久都觉得丑得发嗔，一点都不萌。

第一版 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;
}

结果：

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.

循环次数

其中这个循环的最大次数 100000 是我猜的，应该 160000 靠谱一些。由于图中只有 100 个位置， 又每个位置可能有 4 个方向，所以 john 和 cow 总共有 400 * 400 种状态，循环这个次数就能判断是不是永远追不上了。

修改

我把四个方向直接用 int，四个方向的运动直接用数组表示，不再写一堆条件了。只写一个 move 函数，状态也就是 x、y、dir 就可以描述了，传这三个参就够了。至于
farmer 和 cow，由给什么实参决定。好看多了~

/*
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}; //四个方向move对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;
}