A honeycomb is a mass wax cells built by honey bees, which can be described as a regular tiling of the Euclidean plane, in which three hexagons meet at each internal vertex. The internal angle of a hexagon is 120120 degrees, so three hexagons at a point make a full 360360 degrees. The following figure shows a complete honeycomb with 33 rows and 44 columns.
?
Here we guarantee that the first cell in the second column always locates in the bottom right side of the first cell in the first column, as shown above. A general honeycomb may, on the basis of a complete honeycomb, lose some walls between adjacent cells, but the honeycomb is still in a closed form. A possible case looks like the figure below.
?
Hamilton is a brave bee living in a general honeycomb. Now he wants to move from a starting point to a specified destination. The image below gives a feasible path in a 3×43×4 honeycomb from the 11-st cell in the 22-nd column to the 11-st cell in the 44-th column.
?
Please help him find the minimum number of cells that a feasible path has to pass through (including the starting point and the destination) from the specified starting point to the destination.
Input
The input contains several test cases, and the first line contains a positive integer TT indicating the number of test cases which is up to 104104.
For each test case, the first line contains two integers rr and cc indicating the number of rows and the number of columns of the honeycomb, where 2≤r,c≤1032≤r,c≤103.
The following (4r+3)(4r+3) lines describe the whole given honeycomb, where each line contains at most (6c+3)(6c+3) characters. Odd lines contain grid vertices represented as plus signs ("+") and zero or more horizontal edges, while even lines contain two or more diagonal edges. Specifically, a cell is described as 66 vertices and at most 66 edges. Its upper boundary or lower boundary is represented as three consecutive minus signs ("-"). Each one of its diagonal edges, if exists, is a single forward slash ("/") or a single backslash ("\") character. All edge characters will be placed exactly between the corresponding vertices. At the center of the starting cell (resp. the destination), a capital "S" (resp. a capital "T") as a special character is used to indicate the special cell. All other characters will be space characters. Note that if any input line could contain trailing whitespace, that whitespace will be omitted.
We guarantee that all outermost wall exist so that the given honeycomb is closed, and exactly one "S" and one "T" appear in the given honeycomb. Besides, the sum of r?cr?c in all test cases is up to 2×1062×106.
Output
For each test case, output a line containing the minimum number of cells that Hamilton has to visit moving from the starting cell ("S") to the destination ("T"), including the starting cell and the destination. If no feasible path exists, output -1 instead.
Example
Input
1
3 4
+---+ +---+
/ \ / + +---+ +---+
\ \ / + + S +---+ T +
/ \ / /
+ +---+ + +
\ \ / +---+ +---+ +
/ /
+ +---+ + +
\ / +---+ +---+ +
\ / \ /
+---+ +---+
Output
7从S走到T，求走过的最少房间数（起始房间和终止房间也算）。有六个方向可以走，因为蜜蜂每次都会走到房间的中心位置，所以可以写出方向数组。从一个房间走到另一个房间，需要判断要走的那个房间有没有走过，如果那个房间没有走过，再去判断要走的那个房间是不是封闭的，如果不是，就压入队列，然后BFS搜索就好了。
写完之后去提交，发现WA2，那天晚上刚好看到xx学长过了这道题，就讨论了一下，以为自己题意理解错了，过了几天又开始写这道题，刚好碰到xx学长了，就又问了一下题意，发现自己题意没有问题，后来准备重写了，但又觉得自己的思路没错，然后自己开始找bug，发现方向数组写错了，改了之后T5，xx学长说改个memset数组就好了，改了之后就A了。xx学长tql。
AC代码
1 #include <bits/stdc++.h> 3 using namespace std; 4 const int maxn = 1e3+10; 5 char graph[4*maxn+10][6*maxn+10]; 6 bool vis[4*maxn+10][6*maxn+10]; 7 int dir[6][2] = {{4,0},{-4,0},{-2,-6},{-2,6},{2,-6},{2,6}}; 8 ///下 上 左上 右上 左下 右下 9 struct node{ 10 int x,y; 11 int step; 12 }; 13 int r,c; 14 bool check(int x,int y){ 15 return x >= 0 && x < 4*r+3 && y >= 0 && y < 6*c+3; 16 } 17 void bfs(node st){ 18 node now; 19 queue<node>q; 20 while(!q.empty()) q.pop(); 21 for(int i = 0; i <= 4*r+3; i++) 22 for(int j = 0; j <= 6*c+3; j++){ 23 vis[i][j] = false; 24 } 25 vis[st.x][st.y] = true; 26 q.push(st); 27 while(!q.empty()){ 28 now = q.front(); 29 q.pop(); 30 if(graph[now.x][now.y] == ‘T‘){ 31 printf("%d\n",now.step+1); 32 return ; 33 } 34 for(int i = 0; i < 6; i++){ 35 int x = now.x + dir[i][0]; 36 int y = now.y + dir[i][1]; 37 if(check(x,y)&&!vis[x][y]){ 38 if(i == 0){///down 39 if(graph[now.x+2][now.y]!=‘-‘){ 40 vis[x][y] = true; 41 q.push((node){x,y,now.step+1}); 42 } 43 } 44 else if(i == 1){///up 45 if(graph[now.x-2][now.y]!=‘-‘){ 46 vis[x][y] = true; 47 q.push((node){x,y,now.step+1}); 48 } 49 } 50 else if(i == 2){///左上 51 if(graph[now.x-1][now.y-3]!= ‘\/‘){ 52 vis[x][y] = true; 53 q.push((node){x,y,now.step+1}); 54 } 55 } 56 else if(i == 3){///右上 57 if(graph[now.x-1][now.y+3]!=‘\\‘){ 58 vis[x][y] = true; 59 q.push((node){x,y,now.step+1}); 60 } 61 } 62 else if(i == 4){///左下 63 if(graph[now.x+1][now.y-3]!=‘\\‘){ 64 vis[x][y] = true; 65 q.push((node){x,y,now.step+1}); 66 } 67 } 68 else if(i == 5){///右下 69 if(graph[now.x+1][now.y+3]!=‘\/‘){ 70 vis[x][y] = true; 71 q.push((node){x,y,now.step+1}); 72 } 73 } 74 } 75 } 76 } 77 printf("-1\n"); 78 return ; 79 } 80 int main(){ 81 int T; 82 node s; 83 ///freopen("in.txt","r",stdin); 84 ///freopen("out.txt","w",stdout); 85 scanf("%d",&T); 86 while(T--){ 87 scanf("%d%d",&r,&c); 88 getchar(); 89 for(int i = 0; i < 4*r+3; i++){ 90 gets(graph[i]); 91 } 92 for(int i = 0; i < 4*r+3; i++){ 93 for(int j = 0; j < 6*c+3; j++){ 94 if(graph[i][j] == ‘S‘){ 95 s.x = i,s.y = j,s.step = 0; 96 break; 97 } 98 } 99 } 100 bfs(s); 101 } 102 return 0; 103 }
原文：https://www.cnblogs.com/jyzmlc/p/14700613.html