2018焦作ICPC F. Honeycomb(bfs)-白红宇

2018焦作ICPC F. Honeycomb(bfs)

阅读量：748 次

发布时间：2019-03-22

本文共 799 字，大约阅读时间需要 2 分钟。

思路：比较简单的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
    
      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<
     
      <
      
       =0 && fx
       
        =0 && fy
        
         >T; while(T--){ cin>>n>>m; n=4*n+3; m=6*m+3; getchar(); for(int i=0;i