生活随笔
收集整理的這篇文章主要介紹了
Honeycomb Gym - 102028F（bfs）
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
題目比較嚇人，但是就是一個6個方向的bfs，找最短路徑，優(yōu)先隊列保存。初始化的時候不要用memset，會超時。
代碼如下：
#include<bits/stdc++.h>
#define ll long long
using namespace std
;const int maxx
=6e3+100;
char s
[maxx
][maxx
];
int vis
[maxx
][maxx
];
int d
[][2]={{2,0},{-2,0},{1,3},{-1,3},{1,-3},{-1,-3}};
struct node
{int x
,y
,cnt
;node(int a
,int b
,int c
){x
=a
,y
=b
,cnt
=c
;}bool operator<(const node
&a
)const{return cnt
>a
.cnt
;}
};
int n
,m
,sx
,sy
,ex
,ey
;inline void init()
{for(int i
=0;i
<=n
;i
++)for(int j
=0;j
<=m
;j
++) vis
[i
][j
]=0;
}
inline void bfs(int sx
,int sy
)
{priority_queue
<node
> p
;vis
[sx
][sy
]=1;p
.push(node(sx
,sy
,0));while(p
.size()){node a
=p
.top();p
.pop();if(a
.x
==ex
&&a
.y
==ey
){printf("%d\n",a
.cnt
+1);return ;}for(int i
=0;i
<6;i
++){int tx
=a
.x
+d
[i
][0];int ty
=a
.y
+d
[i
][1];int nx
=a
.x
+2*d
[i
][0];int ny
=a
.y
+2*d
[i
][1];if(nx
<0||nx
>=n
||ny
<0||ny
>=m
) continue;if(vis
[nx
][ny
]==0&&s
[tx
][ty
]==' '){vis
[nx
][ny
]=1;p
.push(node(nx
,ny
,a
.cnt
+1));}}}printf("-1\n");
}
int main()
{int t
;scanf("%d",&t
);while(t
--){scanf("%d%d",&n
,&m
); n
=n
*4+3;m
=m
*6+3;getchar(); for(int i
=0;i
<n
;i
++) gets(s
[i
]);init();for(int i
=0;i
<n
;i
++){for(int j
=0;j
<m
;j
++){if(s
[i
][j
]=='S') sx
=i
,sy
=j
;else if(s
[i
][j
]=='T') ex
=i
,ey
=j
;}}bfs(sx
,sy
);}
}
努力加油a啊，(o)/~
總結
以上是生活随笔為你收集整理的Honeycomb Gym - 102028F（bfs）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
