Massive Algorithms: The Tamworth Two

The Tamworth Two - USACO 2.4.1

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

Lines 1-10:

Ten lines of ten characters each, as explained above

SAMPLE INPUT (file ttwo.in)

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

OUTPUT FORMAT

A single line with the integer number of minutes until Farmer John and the cows meet. Print 0 if they will never meet.

SAMPLE OUTPUT (file ttwo.out)

http://qingtangpaomian.iteye.com/blog/1635842
这道题目的直接模拟即可，有一个小问题在于程序何时停止：1.牛与农民相遇时停止，这种情况比较简单，当农民与牛的坐标相同即可。2.永远不可能相遇时停止，那么如何判断永远不可能相遇。我们使用一个状态数组记录牛、农民、以及他们运动的方向，如果当前牛、农民、以及他们运动的方向曾今出现在状态数组中，那么表示当前的这个状态之前出现过，也就是出现了循环，程序应当停止，并且输出0。
X.
http://qingtangpaomian.iteye.com/blog/1635842
http://sdjl.me/index.php/archives/103

    private static int fFacing = 0;//人的面向，0表示北，1表示东，2表示南，3表示西
    private static int cFacing = 0;//牛的面向，同上
    private static char[][] forestMap = new char[10][10];//森林地图
    private static int fX, fY, cX, cY;//人和牛的坐标
    private static int minutes = 0;//模拟运行的时间
    private static int answer;//输出的结果
    private static boolean[][][][][][] appeared = new boolean[10][10][4][10][10][4];//记录某种状态是否出现过，前3个参数分别是人的x坐标、y坐标、面向，而后3个参数是牛的

    public static void main(String[] args) throws IOException
    {
        init();
        run();
        output();
        System.exit(0);
    }

    private static void run()
    {
        //当人和牛没有遇见且此状态没有出现过
        while ((!meet()) && (stateNotAppeared()))
        {
            //模拟进入下一分钟
            enterNextMinute();
        }
        //如果他们见面了
        if (meet())
        {
            //输出所用时间
            answer = minutes;
        }
        else//否则没有见面
        {
            //输出0
            answer = 0;
        }
    }
    //进入下一分钟
    private static void enterNextMinute()
    {
        if (canMove(fX, fY, fFacing))
        {
            fMove();
        }
        else
        {
            fRotate();
        }

        if (canMove(cX, cY, cFacing))
        {
            cMove();
        }
        else
        {
            cRotate();
        }

        minutes++;
    }
    //根据坐标与面向判断能否前进
    private static boolean canMove(int x, int y, int facing)
    {
        boolean retCanMove = true;

        switch (facing)
        {
            case 0:
                if ((x == 0) || (forestMap[x - 1][y] == '*'))
                {
                    retCanMove = false;
                }
                break;
            case 1:
                if ((y == 9) || (forestMap[x][y + 1] == '*'))
                {
                    retCanMove = false;
                }
                break;
            case 2:
                if ((x == 9) || (forestMap[x + 1][y] == '*'))
                {
                    retCanMove = false;
                }
                break;
            case 3:
                if ((y == 0) || (forestMap[x][y - 1] == '*'))
                {
                    retCanMove = false;
                }
                break;
        }
        return retCanMove;
    }
    //人前进一步
    private static void fMove()
    {
        switch (fFacing)
        {
            case 0:
                fX--;
                break;
            case 1:
                fY++;
                break;
            case 2:
                fX++;
                break;
            case 3:
                fY--;
                break;
        }
    }
    //牛前进一步
    private static void cMove()
    {
        switch (cFacing)
        {
            case 0:
                cX--;
                break;
            case 1:
                cY++;
                break;
            case 2:
                cX++;
                break;
            case 3:
                cY--;
                break;
        }
    }
    //人旋转
    private static void fRotate()
    {
        fFacing = (fFacing + 1) % 4;
    }
    //牛旋转
    private static void cRotate()
    {
        cFacing = (cFacing + 1) % 4;
    }
    //判断是否相遇，相遇返回true
    private static boolean meet()
    {
        if ((fX == cX) && (fY == cY))
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    //判断此状态是否出现过，没出现过返回true
    private static boolean stateNotAppeared()
    {
        if (appeared[fX][fY][fFacing][cX][cY][cFacing])
        {
            return false;
        }
        else
        {
            appeared[fX][fY][fFacing][cX][cY][cFacing] = true;
            return true;
        }
    }

http://www.cppblog.com/jericho/archive/2010/12/08/135786.html
http://martox.eu/2013/usaco-2-4-the-tamworth-two-cpp-solution/

const int MAX = 10000000;

int dx[] = { -1, 0, 1, 0 };

int dy[] = { 0, 1, 0, -1 };

int cd=0, cx, cy;

int fd=0, fx, fy;

int map[10][10];

int main(){

int i,j;

char ch;

fin.open("ttwo.in");

fout.open("ttwo.out");

for(i=0; i<10; i++)

for(j=0; j<10; j++){

fin>>ch;

if(ch=='*'){

map[i][j]=1;

}else if(ch=='C'){

cx=i, cy=j;

}else if(ch=='F'){

fx=i, fy=j;

}

int step=0;

int x,y;

while(step!=MAX){

// for cows

x = cx+dx[cd];

y = cy+dy[cd];

if(map[x][y]==1 || x<0 || x>9 || y<0 || y>9)

cd = (cd+1)%4;

else{

cx = x;

cy = y;

}

// for farmer

x = fx+dx[fd];

y = fy+dy[fd];

if(map[x][y]==1 || x<0 || x>9 || y<0 || y>9)

fd = (fd+1)%4;

else{

fx = x;

fy = y;

}

step++;

//compare

if(cx==fx && cy==fy)

break;

}

if(step == MAX)

fout<<0<<endl;

else

fout<<step<<endl;

return 0;

}

http://qingtangpaomian.iteye.com/blog/1635842
Read full article from thetamworthtwo - codetrick