【HDU 5335】Walk Out（BFS）

分类：DFS、DFS

这道题卡时间卡的比较紧。

一开始直接BFS 毫无疑问的超时，之后想到根据BFS的常规优化思想，去选择起始点进行遍历。

这样我们一开始先BFS一次，这次的BFS是选择出这一点为1并且从起点到这一个点，中间路径的点全为0的点。

这样选择出这个点之后，这个点到终点的路径长度就可以断定了。

之后我们把所有到终点距离最小的点放在一个容器里进行BFS。

这道题没有做出来的原因很大一部分就是对BFS的理解不够深以及该有的贪心思路没有，导致了这道题没有AC。

嗯，有句话说的对：综合是第一生产力。

#include<queue>#include<cstdio>#include<string>#include<cstring>#include<iostream>#include<algorithm>using namespace std;const int maxn = 1005;const int maxd = 1000005;const int INF = (1 << 30);int n,m;char mat[maxn][maxn];const int dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};bool vis[maxn][maxn];int min_dist;vector<int>v0,v1,vv;int path[maxd];int cnt,ok;void bfs_init(){queue<int>q,_q;q.push(0);vis[0][0] = true;while(!q.empty()){int pos = q.front(); q.pop();int x = pos / m, y = pos % m;if(mat[x][y] == '1'){_q.push(pos);min_dist = min(min_dist,n + m – x – y);continue;}if(x == n – 1 && y == m – 1){ok = 1;return;}for(int i = 0; i < 4; i++){int _x = x + dir[i][0];int _y = y + dir[i][1];if(_x >= 0 && _x < n && _y >= 0 && _y < m && !vis[_x][_y]){vis[_x][_y] = true;q.push(_x * m + _y);}}}while(!_q.empty()){int pos = _q.front(); _q.pop();int x = pos / m ,y = pos % m;if((n + m – x – y) == min_dist){vv.push_back(pos);}}}void bfs(){path[0] = 1;for(int i = 1; i < min_dist – 1; i++){int Size = vv.size();for(int j = 0; j < Size; j++){int x = vv[j] / m, y = vv[j] % m;for(int d = 0; d < 2; d ++){int _x = x + dir[d][0];int _y = y + dir[d][1];if(_x >= 0 && _x < n && _y >= 0 && _y < m && !vis[_x][_y]){vis[_x][_y] = true;if(mat[_x][_y] == '0')v0.push_back(_x * m + _y);elsev1.push_back(_x * m + _y);}}}if(v0.empty()){path[cnt++] = 1;vv = v1;v1.clear();}else{path[cnt++] = 0;vv = v0;v0.clear();v1.clear();}}}void init(){min_dist = INF;memset(vis,false,sizeof(vis));v0.clear();v1.clear();vv.clear();cnt = 1;ok = 0;}int main(){int T;scanf("%d",&T);while(T–){scanf("%d%d",&n,&m);init();for(int i = 0; i < n; i++)scanf("%s",mat[i]);bfs_init();if(ok)printf("0\n");else{bfs();for(int i = 0; i < cnt; i++)printf("%d",path[i]);puts("");}}return 0;}

上一篇【HDU 2586】LCA模板

顶0踩0

让情谊在笑声中升腾，当朋友遇到了难题的时候，

相关文章：

你感兴趣的文章：

标签云：