USACO - 2.4.1 - The Tamworth Two

 

原创文章转载请注明出处

摘要：模拟

一. 题目翻译

1. 描述：

两只牛逃跑到了森林里。农夫John开始用他的专家技术追捕这两头牛。你的任务是模拟他们的行为(牛和John)。

追击在10x10的平面网格内进行。一个格子可以是：

一个障碍物, 两头牛(它们总在一起), 或者 农民John. 两头牛和农民John可以在同一个格子内(当他们相遇时)，但是他们都不能进入有障碍的格子。

一个格子可以是：

          . 空地

          * 障碍物

          C 两头牛

          F 农民John

这里有一个地图的例子：

*...*.....

......*...

...*...*..

..........

...*.F....

*.....*...

...*......

..C......*

...*.*....

.*.*......

    

牛在地图里以固定的方式游荡。每分钟，它们可以向前移动或是转弯。如果前方无障碍(地图边沿也是障碍)，它们会按照原来的方向前进一步。否则它们会用这一分钟顺时针转90度。 同时，它们不会离开地图。

农民John深知牛的移动方法，他也这么移动。

每次(每分钟)农民John和两头牛的移动是同时的。如果他们在移动的时候穿过对方，但是没有在同一格相遇，我们不认为他们相遇了。当他们在某分钟末在某格子相遇，那么追捕结束。

读入十行表示农夫John,两头牛和所有障碍的位置的地图。每行都只包含10个字符，表示的含义和上面所说的相同，你可以确定地图中只有一个'F'和一个'C'.'F'和'C'一开始不会处于同一个格子中。

计算农夫John需要多少分钟来抓住他的牛，假设牛和农夫John一开始的行动方向都是正北（即上）。 如果John和牛永远不会相遇，输出0。

2. 格式：

          INPUT FORMAT:

          第1-10行:

          每行10个字符，表示如上文描述的地图。

          OUTPUT FORMAT:

          输出一个数字，表示John需要多少时间才能抓住牛们。如果John无法抓住牛，则输出0。

3. SAMPLE：

          SAMPLE INPUT:

*...*.....

......*...

...*...*..

..........

...*.F....

*.....*...

...*......

..C......*

...*.*....

.*.*......

          SAMPLE OUTPUT:

49

二.  题解

1. 题意理解（将问题分析清楚，大致用什么思路）：

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

 

2. 具体实现（具体实现过程中出现的问题）：

        请参考代码注释。

3. 启示:

判断循环的基本做法就是状态记录，这个需要大家积累一下，2.4.5的题目类似，大家可以对比记忆。

三.  代码

/*
ID:fightin1
LANG:JAVA
TASK:ttwo
*/
package session_2_4_1;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.PrintWriter;
import java.util.Scanner;

public class ttwo {
	
	static char[][] maze = new char[10][10];//迷宫数组
	static int[][] cow = new int[2][2];//牛在迷宫数组中的位置
	static int[][] farmer = new int[2][2];//农民在迷宫数组中的位置
	static boolean[][][][][][] stats = new boolean[10][10][4][10][10][4];//用来记录出现过的状态的为true则表示来过这个状态，参数分别为牛的x坐标、牛的y坐标、牛的方向，农民的x坐标、农民的y坐标、农民的方向。
	static final int NORTH = 0;
	static final int EAST = 1;
	static final int SOUTH = 2;
	static final int WEST = 3;
	
	public static void main(String[] args) throws Exception {
//		Scanner in = new Scanner(System.in);
//		PrintWriter pw = new PrintWriter(System.out);
		
		Scanner in = new Scanner(new BufferedReader(new FileReader(
		"ttwo.in")));
		PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter(
		"ttwo.out")));
		
		//读入迷宫、农民、牛的初始状态
		for (int i=0;i<10;i++){
			String line = in.nextLine();
			for (int j=0;j<10;j++){
				char temp = line.charAt(j);
				if (temp=='C'){
					cow[1][0] = i;
					cow[1][1] = j;
				} 
				if (temp=='F'){
					farmer[1][0] = i;
					farmer[1][1] = j;
				}
				maze[i][j] = temp;
			}
		}
		int cnt = 0;
		int cowDirection = NORTH;//牛的初始方向
		int farmerDirection = NORTH;//农民的初始移动方向
		
		//如果牛与农民相遇则停止。或者牛和农民的状态发生了循环，则两者永远不可能相遇，这时程序停止
		while(!stop()&&!loop(cowDirection, farmerDirection)){
			cowDirection = cowMove(cowDirection);//当前牛的运动方向
			farmerDirection = farmerMove(farmerDirection);//当前农民的运动方向
			cnt++;
		}
		
		if (stop()){
			pw.println(cnt);
		} else {
			pw.println(0);
		}
		
		pw.close();
	}
	
	public static int cowMove(int direction){
		int nextDirection = direction;
		if (direction == NORTH){
			if (cow[1][0]<=0){
				nextDirection = EAST;
			} else {
				if (maze[cow[1][0]-1][cow[1][1]]=='*'){
					nextDirection = EAST;
				} else {
					cow[1][0]--; 
				}
			}
		} else if (direction == SOUTH){
			if (cow[1][0]>=9){
				nextDirection = WEST;
			} else {
				if (maze[cow[1][0]+1][cow[1][1]]=='*'){
					nextDirection = WEST;
				} else {
					cow[1][0]++;
				}
			}
		} else if (direction == WEST){
			if (cow[1][1]<=0){
				nextDirection = NORTH;
			} else {
				if (maze[cow[1][0]][cow[1][1]-1]=='*'){
					nextDirection = NORTH;
				} else {
					cow[1][1]--;
				}
			}
		} else if (direction == EAST){
			if (cow[1][1]>=9){
				nextDirection = SOUTH;
			} else {
				if (maze[cow[1][0]][cow[1][1]+1]=='*'){
					nextDirection = SOUTH;
				} else {
					cow[1][1]++;
				}
			}
		}
		return nextDirection;
	}
	
	public static int farmerMove (int direction){
		int nextDirection = direction;
		if (direction == NORTH){
			if (farmer[1][0]<=0){
				nextDirection = EAST;
			} else {
				if (maze[farmer[1][0]-1][farmer[1][1]]=='*'){
					nextDirection = EAST;
				} else {
					farmer[1][0]--;
				}
			}
		} else if (direction == SOUTH){
			if (farmer[1][0]>=9){
				nextDirection = WEST;
			} else {
				if (maze[farmer[1][0]+1][farmer[1][1]]=='*'){
					nextDirection = WEST;
				} else {
					farmer[1][0]++;
				}
			}
		} else if (direction == WEST){
			if (farmer[1][1]<=0){
				nextDirection = NORTH;
			} else {
				if (maze[farmer[1][0]][farmer[1][1]-1]=='*'){
					nextDirection = NORTH;
				} else {
					farmer[1][1]--;	
				}
			}
		} else if (direction == EAST){
			if (farmer[1][1]>=9){
				nextDirection = SOUTH;
			} else {
				if (maze[farmer[1][0]][farmer[1][1]+1]=='*'){
					nextDirection = SOUTH;
				} else {
					farmer[1][1]++;
				}
			}
		}
		return nextDirection;
	}
	
	//农民与牛相遇
	public static boolean stop(){
		if ((cow[1][0]==farmer[1][0])&&(cow[1][1]==farmer[1][1])){
			return true;
		} else {
			return false;
		}
	}
	
	//发生了循环，当前状态曾经出现过
	public static boolean loop(int cowDirection ,int farmerDirection){
		if (stats[cow[1][0]][cow[1][1]][cowDirection][farmer[1][0]][farmer[1][1]][farmerDirection]){
			return true;
		} else {
			stats[cow[1][0]][cow[1][1]][cowDirection][farmer[1][0]][farmer[1][1]][farmerDirection] = true;
			return false;
		}
	}
}