洛谷 P1518 [USACO2.4]两只塔姆沃斯牛 The Tamworth Two

太巧妙了~

题目链接：https://www.luogu.com.cn/problem/P1518

做的时候在如何转弯这个地方难住了，还有什么时候循环结束也不知道怎么判断，，太蒻了；

分析：

1、由于牛和人都不能出圈，所以很容易想到在整个地图的外一圈再加上一圈 障碍物，这样的话就不用判断边界了。

2、如何转弯？设置两个数组，分别表示人和牛， 由于一开始是朝北走的，所以设0代表北，1代表东，2代表南，3代表西，在移动的时候，肯定是人和牛同时移动的（毋庸置疑）。

　  那么先判断再往前走一格的话会不会遇到障碍物，如果是障碍物，那么就要转弯了，所以我们还需要设置一个变量，来标记是朝哪个方向转弯，很巧妙的是，题解中c[0]和f[0]都

　  没有用到，所以刚好可以用他们来表示朝向，而且不会混淆。

3、如何判断结束？有两个情况： 一是人和牛的坐标相同，这代表他们相遇了，那么人就抓到牛了，所以程序停止。 二是人和牛一直不相遇，那么就会无限走下去，这时候我们需要

　  找到某种关系（这个我真的想不出来）。下面贴出别人的解释（在我以后因此疑惑的时候，便于帮我理解）。

 以下是别人的解释：

农夫的x坐标+他的y坐标*10+奶牛的x坐标*100+奶牛的y坐标* 1000+农夫的方向*10000+奶牛的方向*40000（农夫方向最多为4） 这里面权重的取值很关键! 权重分别为 1 10 100 1000 10000 40000，包括了所有的情况. 意味着, 个位数的值 只与 农夫的X 坐标挂钩,因为其他的部分都不会影响个位数的取值,同理 十位数与 Y 挂钩, 其他的也是 而 10000 与 40000, 因为前面是坐标,而地图大小为 10*10 , 有0-9(或者1- 10) 10种可能, 而后面两个是方向 上下左右只需要四个值即可表示 0 1 2 3，因此 最后一项的权重是 40000(当然你×100000应该也没问题,但是40000更小节约内存嘛) 这样,将每一种情况都保存起来, 确保不会出现重复 (出现重复,则说明牛和农夫在绕圈子 , 永远也走不到一起,即捕捉失败)

代码+注释：

#include 
using namespace std;
char m[12][12];  // 地图 
int f[3], c[3], ans, flag;   // f、c 是人和牛的位置,以及朝向,ans是时间 
bool zt[160005];

void move(int x, int y, int fx, int who)
{
    if(fx == 0)
    {
        if(m[x-1][y] == '*') if(who == 0) f[0] = 1; else c[0] = 1;
        else if(who == 0) f[1]--; else c[1]--;
    }
    else if(fx == 1)
    {
        if(m[x][y+1] == '*') if(who == 0) f[0] = 2; else c[0] = 2;
        else if(who == 0) f[2]++; else c[2]++;
    }
    else if(fx == 2)
    {
        if(m[x+1][y] == '*') if(who == 0) f[0] = 3; else c[0] = 3;
        else if(who == 0) f[1]++; else c[1]++;
    }
    else
    {
        if(m[x][y-1] == '*') if(who == 0) f[0] = 0; else c[0] = 0;
        else if(who == 0) f[2]--; else c[2]--;
    }
}

bool pd()  // 判断相遇 
{
    if(f[1] == c[1] && f[2] == c[2]) return 0;
    else return 1;
}

int main()
{
    for(int i = 0; i <= 11; i++) m[i][0] = '*', m[0][i] = '*', m[i][11] = '*', m[11][i] = '*';  // 加上外围，避免判断边界 
    for(int i = 1; i <= 10; i++)
    {
        for(int j = 1; j <= 10; j++)
        {
            cin >> m[i][j];
            if(m[i][j] == 'F') f[1] = i, f[2] = j;
            if(m[i][j] == 'C') c[1] = i, c[2] = j;
        }
    } 
    while(pd())
    {
        flag = f[1] + f[2]*10 + c[1]*100 + c[2]*1000 + f[0]*10000 + c[0]*40000;
        if(zt[flag])
        {
            cout << 0 << endl;
            return 0;
        }
        zt[flag] = 1;
        move(f[1], f[2], f[0], 0);
        move(c[1], c[2], c[0], 1);
        ans++;
    }
    cout << ans << endl;
    return 0;
}