#1094 : Lost in the City
描述
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
算法分析：在大地图中找子地图，注意：子地图的方向不确定，也就是说，子地图可以旋转4次90度，产生4中形态。 只要大地图中，有其中任意一种形态，那个位置就是合法的。找出所有这样的状态。 一开始我想把子地图存储成二维数组，后来发现要把它变换成共4中形态，变换的语句描述很是麻烦，修饰语法就得写一大堆。 为了一下xu建哥有什么好的策略：可以把子图存储成一维数组。然后按照四中形态的遍历顺序去大地图中进行遍历。看看在 当前的i,j，能不能遍历出这样的序列，如果能就说明这个位置合法，直接输出。否则继续枚举寻找。1 #include <stdio.h> 2 #include <string.h> 3 #include <string> 4 #include <iostream> 5 #include <algorithm> 6 #include <ctype.h> 7 8 using namespace std; 9 10 char ch[202][202]; 11 char c[11]; 12 13 bool test_ok(int dd, int ff) 14 { 15 int i, j; 16 int k=0; 17 int ok=1; 18 for(i=dd; i<=dd+2; i++) 19 { 20 for(j=ff; j<=ff+2; j++) 21 { 22 if(ch[i][j]==c[k]) 23 { 24 k++; 25 } 26 else 27 { 28 ok=0; break; 29 } 30 } 31 if(ok==0) 32 break; 33 } 34 if(ok==1) 35 { 36 return true; 37 } 38 ok=1; k=0; 39 for(j=ff; j<=ff+2; j++) 40 { 41 for(i=dd+2; i>=dd; i--) 42 { 43 if(ch[i][j]==c[k]) 44 k++; 45 else 46 { 47 ok=0; break; 48 } 49 } 50 if(ok==0) 51 break; 52 } 53 if(ok==1) 54 return true; 55 56 ok=1; k=0; 57 for(i=dd+2; i>=dd; i--) 58 { 59 for(j=ff+2; j>=ff; j--) 60 { 61 if(ch[i][j]==c[k]) 62 k++; 63 else 64 { 65 ok=0; break; 66 } 67 } 68 if(ok==0) 69 break; 70 } 71 if(ok==1) 72 return true; 73 74 ok=1; k=0; 75 for(j=ff+2; j>=ff; j--) 76 { 77 for(i=dd; i<=dd+2; i++) 78 { 79 if(ch[i][j]==c[k]) 80 k++; 81 else 82 { 83 ok=0; break; 84 } 85 } 86 if(ok==0) 87 break; 88 } 89 if(ok==1) 90 return true; 91 92 return false; 93 } 94 95 int main() 96 { 97 int n, m; 98 scanf("%d %d", &n, &m); 99 int i, j; 100 char cc; 101 for(i=0; i<n; i++) 102 { 103 for(j=0; j<m; j++) 104 { 105 cc=getchar(); 106 while(!isalpha(cc)&&cc!='.' ) //不是字母且不是. 107 { 108 cc=getchar(); 109 } 110 ch[i][j]=cc; 111 } 112 } //建立地图 113 int e=0; 114 for(i=0; i<3; i++) 115 for(j=0; j<3; j++) 116 { 117 cc=getchar(); 118 while(!isalpha(cc)&&cc!='.') 119 cc=getchar(); 120 c[e++]=cc; 121 } 122 c[e]='\0'; 123 //printf("%s", c); 124 //建立小地图 125 for(i=0; i<=n-3; i++) 126 { 127 for(j=0; j<=m-3; j++) 128 { 129 if(test_ok(i, j)) 130 { 131 printf("%d %d\n", i+1+1, j+1+1); 132 } 133 } 134 } 135 return 0; 136 }
