A pair of cows is loose somewhere in the forest. Farmer John is lending his expertise to their capture. Your task is to model their behavior.

The chase takes place on a 10 by 10 planar grid. Squares can be empty or they can contain:

• an obstacle,
• the cows (who always travel together), or
• Farmer John.

The cows and Farmer John can occupy the same square (when they `meet') but neither the cows nor Farmer John can share a square with an obstacle.

Each square is represented as follows: . Empty square * Obstacle C Cows F Farmer

Here is a sample grid: *...*..... ......*... ...*...*.. .......... ...*.F.... *.....*... ...*...... ..C......* ...*.*.... .*.*......

The cows wander around the grid in a fixed way. Each minute, they either move forward or rotate. Normally, they move one square in the direction they are facing. If there is an obstacle in the way or they would leave the board by walking `forward', then they spend the entire minute rotating 90 degrees clockwise.

Farmer John, wise in the ways of cows, moves in exactly the same way.

The farmer and the cows can be considered to move simultaneously during each minute. If the farmer and the cows pass each other while moving, they are not considered to have met. The chase ends when Farmer John and the cows occupy the same square at the end of a minute.

Read a ten-line grid that represents the initial state of the cows, Farmer John, and obstacles. Each of the ten lines contains exactly ten characters using the coding above. There is guaranteed to be only one farmer and one pair of cows. The cows and Farmer John will not initially be on the same square.

Calculate the number of minutes until the cows and Farmer John meet. Assume both the cows and farmer begin the simulation facing in the `north' direction. Print 0 if they will never meet.

PROGRAM NAME: ttwo

INPUT FORMAT

SAMPLE INPUT (file ttwo.in)

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

OUTPUT FORMAT

SAMPLE OUTPUT (file ttwo.out)

49

题意：
给出地图，f表示农民，c表示牛，开始两者都向东。农民和牛都可以前进或顺时针转向，每个动作花费1分钟。
求何时两者相遇。插身而过不算相遇，要两者走到一起才算相遇。

代码如下：

/*
LANG: C
PROG: ttwo
*/
#include<stdio.h>
char map[10][11];
int fx, fy, cx, cy, fd, cd, time = 0;
int M[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
int sta[10][10][4][10][10][4];//表示状态。 
int Walk(int *x, int *y, int dic)//判断能否行走 
{
    *x += M[dic][0];
    *y += M[dic][1];
    if (*x >= 0 && *x < 10 && *y >= 0 && *y < 10 && map[*x][*y] != '*')
    {
        return 1;
    }
    *x -= M[dic][0];
    *y -= M[dic][1];
    return 0;
}
int Rotate(int *dic)
{
    *dic = (*dic + 1) % 4;
}
int Meet()
{
    if (fx == cx && fy == cy)
    {
        return 1;
    }
    return 0;
}
int Ok()
{
    if (sta[fx][fy][fd][cx][cy][cd])//如果之前走过，且状态相同，则两者不能相遇。 
    {
        return 0;
    }
    sta[fx][fy][fd][cx][cy][cd] = 1;//标记走过 
    return 1;
}
int Run()
{
    if (!Walk(&fx, &fy, fd))//不能走就转向。 
    {
        Rotate(&fd);
    }
    if (!Walk(&cx, &cy, cd))
    {
        Rotate(&cd);
    }
    time++;
    if (!Meet())//两者不相遇 
    {
        if (Ok())
        {            
            return Run();
        }
        else
        {
            return 0;
        }
    }
    else
    {
        return time;
    }
}
int main()
{
    freopen("ttwo.in", "r", stdin);
    freopen("ttwo.out", "w", stdout);
    int i, j;
    for (i = 0; i < 10; i++)
    {
        for (j = 0; j < 10; j++)
        {
            scanf("%c", &map[i][j]);
            if (map[i][j] == 'F')
            {
                fx = i, fy = j, fd = 0;
            }
            else if (map[i][j] == 'C')
            {
                cx = i, cy = j, cd = 0;
            }
        }
        getchar();
        map[i][j] = 0;
    }
    printf("%d\n", Run());
    fclose(stdin);
    fclose(stdout);
    //system("pause");
    return 0;
}