hihoCoder1094LostintheCity.doc

#1094 : Lost in the City时间限制:10000ms单点时限:1000ms内存限制:256MB描述Little Hi gets lost in the city. He does not know where he is. He does not know which direction is north.Fortunately, Little Hi has a map of the city. The map can be considered as a grid of N*M blocks. Each block is numbered by a pair of integers. The block at the north-west corner is (1, 1) and the one at the south-east corner is (N, M). Each block is represented by a character, describing the construction on that block: . for empty area, P for parks, H for houses, S for streets, M for malls, G for government buildings, T for trees and etc.Given the blocks of 3*3 area that surrounding Little Hi(Little Hi is at the middle block of the 3*3 area), please find out the position of him. Note that Little Hi is disoriented, the upper side of the surrounding area may be actually north side, south side, east side or west side.输入Line 1: two integers, N and M(3 = N, M = 200).Line 2N+1: each line contains M characters, describing the citys map. The characters can only be A-Z or .Line N+2N+4: each line 3 characters, describing the area surrounding Little Hi.输出Line 1K: each line contains 2 integers X and Y, indicating that block (X, Y) may be Little His position. If there are multiple possible blocks, output them from north to south, west to east.样例输入8 8.HSH.HSM.HST.HSPP.PPGHSPPTPPSSSSSS.MMSHHH.MMSH.SSSSHGSH.样例输出5 4一、 分析1） 首先我们知道M、N均小于200，这说明问题规模不大，可以采用暴力枚举法，即挨个遍历矩阵中的每个点，若该点与Little hi所处点相同，则将该点的周围3*3范围（比较矩阵）与little hi 周围3*3空间（目标矩阵）比较，若相同，输出该点的坐标，直至遍历整个矩阵。2） 两矩阵判断，由于目标矩阵方向不定，所以必须对目标矩阵的所有可能性都进行判断，才能确定两矩阵是不是相同。这里采用旋转，即将目标矩阵按某一方向旋转（本题中采用顺时针），每次旋转后均为一种可能性，一共有4种情况，即需旋转4次，每次旋转后均与比较矩阵相比，只要存在一种情况相同即可判断出true。3）尽量让一个方法只能实现一个功能，这样可以减少编写难度，同时便于修改。二、 代码import java.util.Scanner;public class Test1094 public static void main(String args) Scanner scan = new Scanner(System.in);int n = scan.nextInt();int m = scan.nextInt();/存储地图数据char maps = new charnm;/注意矩阵下标从零开始，最后横纵坐标需加一for (int i = 0; i n; i+) String s = scan.next().trim();mapsi = s.toCharArray();/存储目标矩阵char location = new char33;for (int i = 0; i 3; i+) String s = scan.next().trim();locationi = s.toCharArray();getResult(maps, location);scan.close();static void getResult(char maps, char location) char c = location11;/ little hi 所处位置的字符for (int i = 0; i maps.length; i+) for (int j = 0; j mapsi.length; j+) if (mapsij = c) /判断是否与little hi所处位置是否相同char temp = getSurround(maps, i, j);/获取比较矩阵if (isLoaction(temp, location) System.out.println(i + 1) + + (j + 1);/根据 x,y生成该点周围的矩阵3*3static char getSurround(char maps, int x, int y) int m = maps.length;int n = maps0.length;char round = new char33;for (int i = 0; i 3; i+) for (int j = 0; j 3; j+) int a = x - 1 + i;int b = y - 1 + j;/若下标越界，该矩阵位置存储空格if (a = m | b = n)roundij = ;elseroundij = mapsab;return round;/判断是否为中心点static boolean isLoaction(char m, char l) char c = m;for (int i = 0; i 4; i+) c = circle(c);if (isSame(c, l)return true;return false;/将矩阵m按顺时针旋转static char circle(char m) char ch = new char33;ch00 = m20;ch01 = m10;ch02 = m00;ch10 = m21;ch11 = m11;ch12 = m01;ch20 = m22;ch21 = m12;ch22 = m02;return ch;/用来判断两矩阵是否相同static boolean isSame(char m, char l) for (int i = 0; i 3; i+) for (int j = 0; j 3; j+) if (mij != lij)return false;return true;