USACO - 1.2.2 - Transformations

转载请注明出处

 

摘要：枚举 

一. 题目翻译

1. 描述：

          一块N x N（1<=N<=10）正方形的黑白瓦片的图案要被转换成新的正方形图案。写一个程序来找出将原始图案按照以下列转换方法转换成新图案的最小方式：

1：转90度：图案按顺时针转90度。

2：转180度：图案按顺时针转180度。

3：转270度：图案按顺时针转270度。

4：反射：图案在水平方向翻转（以中央铅垂线为中心形成原图案的镜像）。

5：组合：图案在水平方向翻转，然后再按照1到3之间的一种再次转换。

6：不改变：原图案不改变。

7：无效转换：无法用以上方法得到新图案。

如果有多种可用的转换方法，请选择序号最小的那个。

2. 格式：

          PROGRAM NAME: transform

          INPUT FORMAT:

          (file transform.in)

          第一行： 单独的一个整数N。

          第二行到第N+1行： N行每行N个字符（不是“@”就是“-”）；这是转换前的正方形。

          第N+2行到第2*N+1行： N行每行N个字符（不是“@”就是“-”）；这是转换后的正方形。

          OUTPUT FORMAT:

          (file transform.out)

          单独的一行包括1到7之间的一个数字（在上文已描述）表明需要将转换前的正方形变为转换后的正方形的转换方法。

3. SAMPLE：

          SAMPLE INPUT:

3

@-@

---

@@-

@-@

@--

--@          

          SAMPLE OUTPUT:

              1

二.  题解

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

          这道题目一共只有9种情况，直接枚举所有情况，然后判断当前图案是否和目标图案相同即可。我的程序写的相对较笨，用了9个boolean的标志位标示每种情况是否满足（初始值都满足，有一位不满足对应关系则赋值false，下一位判断时这种情况就可以直接跳过了），输出的时候按顺序依次判断如果为真则输出。  

2. 需要注意的细节：

          注意每种情况翻转后与未翻转的字符对应关系。eg:第一种情况src[i][j]与src[num - j - 1][i](注意这里的num对应题目中单行最大字符数N)。

三.  代码package session_1_2_2;

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

public class transform {

	/**
	 * @param args
	 */

	public static void main(String[] args) {
		try {
			Scanner in = new Scanner(new BufferedReader(new FileReader(
					"F:\\UCASO\\temp\\transform.in")));
			PrintWriter pw = new PrintWriter(new FileWriter(
					"F:\\UCASO\\temp\\transform.out"));

			int num = Integer.parseInt(in.nextLine());
			char src[][] = new char[num][num];
			boolean s1 = true, s2 = true, s3 = true, s4 = true, s51 = true, s52 = true, s53 = true, s6 = true;
			
			for (int i = 0; i < num; i++) {
				String line = in.nextLine();
				for (int j = 0; j < num; j++) {
					src[i][j] = line.charAt(j);
				}
			}

			for (int i = 0; i < num; i++) {
				String line = in.nextLine();
				for (int j = 0; j < num; j++) {
					char target = line.charAt(j);
					if (s1) {
						if (target == src[num - j - 1][i]) {
							s1 = true;
						} else {
							s1 = false;
						}
					}
					if (s2) {
						if (target == src[num - i - 1][num - j - 1]) {
							s2 = true;
						} else {
							s2 = false;
						}
					}
					if (s3) {
						if (target == src[j][num - i - 1]) {
							s3 = true;
						} else {
							s3 = false;
						}
					}
					if (s4) {
						if (target == src[i][num - j - 1]) {
							s4 = true;
						} else {
							s4 = false;
						}
					}
					if (s51) {
						if (target == src[j][i]) {
							s51 = true;
						} else {
							s51 = false;
						}
					}
					if (s52) {
						if (target == src[num - i - 1][j]) {
							s52 = true;
						} else {
							s52 = false;
						}
					}
					if (s53) {
						if (target == src[num - j - 1][num - i - 1]) {
							s53 = true;
						} else {
							s53 = false;
						}
					}
					if (s6) {
						if (target == src[i][j]) {
							s6 = true;
						} else {
							s6 = false;
						}
					}
				}
			}
			if (s1) {
				pw.println("1");
			} else if (s2) {
				pw.println("2");
			} else if (s3) {
				pw.println("3");
			} else if (s4) {
				pw.println("4");
			} else if (s51 || s52 || s53) {//要注意输出5的话有3种情况
				pw.println("5");
			} else if (s6) {
				pw.println("6");
			} else {
				pw.println("7");
			}
			pw.close();
			in.close();
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
}