F. Honeycomb
思路：比较简单的bfs，我们以每个六边形的中心作为这个六边形的一个整体。很容易看到有六个方向可以走。至于能不能走出去，只需要看六个方向的出口处A是不是空格，是空格的话，假设当前六边形中心为S，要走到的下一个六边形中心为T，容易知道从S走到T的方向和距离就是从S到A的两倍。
坑点：
①如果走不到终点要输出-1，没注意看题目，以为保证能走到，wa了一发
②清空标记数组vis用两个for清空，不要用memset对所有点清空 不然会TLE
#include<bits/stdc++.h> using namespace std; const int N=(1e3+5)*6; int n,m; int dx[]={-1,-1,-2,2,1,1}; int dy[]={-3,3,0,0,-3,3}; char mp[N][N]; bool vis[N][N]; int sx,sy; struct node{ int x,y,st; }; void bfs(){ for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ vis[i][j]=0; } } queue<node> que; que.push({sx,sy,1}); vis[sx][sy]=1; while(!que.empty()){ node now=que.front(); que.pop(); int x=now.x,y=now.y,st=now.st; if(mp[x][y]=='T') { cout<<st<<endl; return ; } for(int i=0;i<6;i++){ int X=x+dx[i]; int Y=y+dy[i]; int fx=X+dx[i]; int fy=Y+dy[i]; if(mp[X][Y]==' ' && fx>=0 && fx<n && fy>=0 && fy<m && !vis[fx][fy] ){ que.push({fx,fy,st+1}); vis[fx][fy]=1; } } } cout<<-1<<endl; } int main(){ int T;cin>>T; while(T--){ cin>>n>>m; n=4*n+3; m=6*m+3; getchar(); for(int i=0;i<n;i++){ gets(mp[i]); for(int j=0;mp[i][j];j++){ if(mp[i][j]=='S'){ sx=i; sy=j; } } } bfs(); } return 0; }