That's clever~

Title Link: https://www.luogu.com.cn/problem/P1518

It's difficult to make a turn, and I don't know how to judge when the cycle ends. It's too konjac;

analysis:

1. Since neither cattle nor people can go out of the circle, it is easy to think of adding a circle of obstacles to the outer circle of the whole map, so there is no need to judge the boundary.

2. How to turn? Set two arrays to represent people and cattle respectively. Since they walk towards the north at the beginning, set 0 to represent the north, 1 to represent the East, 2 to represent the South and 3 to represent the West. When moving, people and cattle must move at the same time (no doubt).

Then, judge whether you will encounter obstacles if you go ahead one grid first. If it is an obstacle, you will have to turn, so we need to set a variable to mark which direction to turn. It is very clever that both c[0] and f[0] in the problem solution

They are not used, so they can be used to indicate the orientation without confusion.

3. How to judge the end? There are two situations: first, the coordinates of people and cattle are the same, which means that they meet, so people catch cattle, so the program stops. Second, if people and cattle never meet, they will go on indefinitely. At this time, we need

Find a relationship (I really can't think of this). The explanation of others is posted below (it is convenient to help me understand when I am confused later).

The following is someone else's explanation:

The farmer's X coordinate + his Y coordinate * 10 + the cow's X coordinate * 100 + the cow's Y coordinate * 1000 + the farmer's direction * 10000 + the cow's direction * 40000 (the farmer's direction is 4 at most). The value of weight is very important! The weights are 1 10 100 1000 10000 40000 respectively, including all cases It means that the value of the single digit is only linked to the farmer's X coordinate, because other parts will not affect the value of the single digit. Similarly, the ten digit is linked to Y, and the others are 10000 and 40000. Because the front is the coordinate, and the map size is 10 * 10, there are 10 possibilities of 0-9 (or 1-10), while the latter two are directions, up, down, left and right. Only four values are required to represent 0 1 2 3, Therefore, the weight of the last item is 40000 (of course you × 100000 should be OK, but 40000 is less to save memory). In this way, save every situation to ensure that there is no repetition (if there is repetition, it means that the cow and the farmer are in a circle and will never get together, that is, the capture fails)

Code + comment:

#include <bits/stdc++.h>
using namespace std;
char m[12][12];  // Map 
int f[3], c[3], ans, flag;   // f,c It's the location of people and cattle,And orientation,ans It's time 
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()  // Judge encounter 
{
    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] = '*';  // Add the periphery to avoid judging the boundary 
    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;
}