2018焦作ICPC F. Honeycomb(bfs)

F. Honeycomb

思路：比较简单的bfs，我们以每个六边形的中心作为这个六边形的一个整体。很容易看到有六个方向可以走。至于能不能走出去，只需要看六个方向的出口处A是不是空格，是空格的话，假设当前六边形中心为S，要走到的下一个六边形中心为T，容易知道从S走到T的方向和距离就是从S到A的两倍。

坑点：

①如果走不到终点要输出-1，没注意看题目，以为保证能走到，wa了一发

②清空标记数组vis用两个for清空，不要用memset对所有点清空 不然会TLE

#include
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;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！