USACO2.4.1 The Tamworth Two Two Tamworth Bulls Problem Report (simulation)

2.4.1 The Tamworth Two Two Tamworth Cows

Time Limit: 1 Sec  Memory Limit: 64 MB Submit: 18  Solved: 14 [Submit][Status][Discuss]

Description

Two cows were deliberately lost in the forest . Farmer John began to hunt down the two cows with his expert skills. Your task is to simulate their behavior (bovine and John). The pursuit is done in a 10x10 planar grid. A grid can be: an obstacle, two cows (they are always together), or a farmer John. Two cows and a farmer John can be in the same grid (when they meet), but they can't enter the barrier grid. A grid can be: . Open space * Obstacle C Two cows F Farmer John Here is an example of a map:

*...*.....
......*...
...*...*..
..........
...*.F....
*.....*...
...*......
..C......*
...*.*....
.*.*......
 

牛 The wandering in a fixed way on the map. Every minute, they can move forward or turn. If the front is barrier-free and will not leave the map, they will go further in the original direction. Otherwise they will use this minute to turn 90 degrees clockwise. The peasant John, who knows how to move the cow, moves so. Every time (every minute) the movement of the farmer John and the two cows is simultaneous. If they cross each other while they are moving, but they don't meet in the same place, we don't think they met. When they meet at a certain grid at the end of a certain minute, the hunt ends. At the beginning, John and the cow were facing the north.

Input

Lines 1-10: 10 characters per line, representing the map as described above.

Output

outputs a number indicating how much time John needs to catch the cows. Output 0 if John can't catch the cow.

Sample Input

*...*.....
......*...
...*...*..
..........
...*.F....
*.....*...
...*......
..C......*
...*.*....
.*.*......

Sample Output

49

Go up from point F and point C. If you can't go, turn clockwise to 90°. Ask how long it takes to double-point

direct simulation. Set a large value to let it reach this value, otherwise it will meet. When jumping out

code is as follows

#include <map>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <fstream>
#include <iostream>
#include <sstream>
#include <algorithm>
#define lowbit(a) (a&(-a))
#define _mid(a,b) ((a+b)/2)
#define debu(a) cout << a <<" ";
#define debug(a) cout << a << endl;
#define _mem(a,b) memset(a,0,(b+3)<<2)
#define fori(a) for(int i=0;i<a;i++)
#define forj(a) for(int j=0;j<a;j++)
#define ifor(a) for(int i=1;i<=a;i++)
#define jfor(a) for(int j=1;j<=a;j++)
#define mem(a,b) memset(a,b,sizeof(a))
#define IN freopen("in.txt","r",stdin)
#define OUT freopen("out.txt","w",stdout)
#define IO do{\
    ios::sync_with_stdio(false);\
    cin.tie(0);\
    cout.tie(0);}while(0)
#define mp(a,b) make_pair(a,b);
using namespace std;
typedef long long ll;
const int maxn =  15;
const int INF = 0x3f3f3f3f;
const int inf = 0x3f;
const double EPS = 1e-7;
const double Pi = acos(-1);
const int MOD = 1e9+7;
char g[maxn][maxn];
int dir[4][2] = {1,0,0,1,-1,0,0,-1};
struct node{
    int x,y,m;
}a,b;
bool juge(int x,int y){return x&&x<=10&&y&&y<=10&&g[x][y]!='*';}
 
void move(node &a){
    if(!juge(a.x+dir[a.m][0],a.y+dir[a.m][1]))
        a.m = (a.m+1)%4;
    else
        a.x+=dir[a.m][0],a.y+=dir[a.m][1];
}
 
void getres(){
    int cnt = 0;
    while(cnt < 5000&&++cnt){
        move(a);
        move(b);
        if(a.x==b.x&&a.y==b.y)
            break;
    }
    cout << (cnt==5000?0:cnt)<<endl;
}
 
int main() {
    int n = 10;
    a.m = b.m = 0;
 
    for(int i=10;i>0;i--)
        jfor(10){
            cin >> g[i][j];
            if(g[i][j]=='F')
                a.x = i,a.y = j;
            else if(g[i][j] == 'C')
                b.x = i,b.y = j;
        }
    getres();
    return 0;
}