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 2~N+1: each line contains M characters, describing the city's map. The characters can only be 'A'-'Z' or '.'.
Line N+2~N+4: each line 3 characters, describing the area surrounding Little Hi.
输出
Line 1~K: each line contains 2 integers X and Y, indicating that block (X, Y) may be Little Hi's position. If there are multiple possible blocks, output them from north to south, west to east.
样例输入
8 8
...HSH..
...HSM..
...HST..
...HSPP.
PPGHSPPT
PPSSSSSS
..MMSHHH
..MMSH..
SSS
SHG
SH.
样例输出
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 char[n][m];
//注意矩阵下标从零开始，最后横纵坐标需加一
for (int i = 0; i < n; i++) {
String s = scan.next().trim();
maps[i] = s.toCharArray();
}
//存储目标矩阵
char[][] location = new char[3][3];
for (int i = 0; i < 3; i++) {
String s = scan.next().trim();
location[i] = s.toCharArray();
}

getResult(maps, location);
scan.close();
}

static void getResult(char[][] maps, char[][] location) {
char c = location[1][1];// little hi 所处位置的字符
for (int i = 0; i < maps.length; i++) {
for (int j = 0; j < maps[i].length; j++) {
if (maps[i][j] == c) {//判断是否与little hi所处位置是否相同
char[][] temp = getSurround(maps, i, j);//获取比较矩阵
if (isLoaction(temp, location)) {
System.out.println((i + 1) + " " + (j + 1));
}
}
}
}
}
//根据 x,y生成该点周围的矩阵3*3
static char[][] getSurround(char[][] maps, int x, int y) {
int m = maps.length;
int n = maps[0].length;
char[][] round = new char[3][3];
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 < 0 || a >= m || b < 0 || b >= n)
round[i][j] = ' ';
else
round[i][j] = maps[a][b];
}
}
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 char[3][3];

ch[0][0] = m[2][0];
ch[0][1] = m[1][0];
ch[0][2] = m[0][0];

ch[1][0] = m[2][1];
ch[1][1] = m[1][1];
ch[1][2] = m[0][1];

ch[2][0] = m[2][2];
ch[2][1] = m[1][2];
ch[2][2] = m[0][2];
return ch;
}
//用来判断两矩阵是否相同
static boolean isSame(char[][] m, char[][] l) {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (m[i][j] != l[i][j])
return false;
}
}
return true;
}
}