首页 > 代码库 > CCF_I’m stuck!_bfs
CCF_I’m stuck!_bfs
题目链接：
http://115.28.138.223:81/view.page?opid=5
思路：
一次bfs从起点开始找到起点能到达的点，一次bfs从终点开始找到能到终点的点，最后输出答案即可。
刚开始写的时候，考虑找起点能到达的点的时候，用了dfs，提交只有20分，仔细想了一下，会存在无限循环的情况。
#include<cstdio>#include<iostream>#include<cstring>#include<queue>using namespace std;struct point{ int x,y;}start,stop;char a[55][55];int r,c,cango[55][55],canfrom[55][55],dir[][2] = {{-1,0},{1,0},{0,-1},{0,1}};void bfs1(point start){ queue<point> q; q.push(start); while(!q.empty()) { int x = q.front().x,y = q.front().y; q.pop(); if(x<0 || x>=r || y<0 || y>=c || a[x][y]==‘#‘ || cango[x][y]) continue; cango[x][y] = 1; if(a[x][y]==‘S‘ || a[x][y]==‘T‘ || a[x][y]==‘+‘) { for(int i = 0;i < 4;i++) { point temp; temp.x = x+dir[i][0]; temp.y = y+dir[i][1]; q.push(temp); } } else if(a[x][y] == ‘-‘) { for(int i = 2;i < 4;i++) { point temp; temp.x = x+dir[i][0]; temp.y = y+dir[i][1]; q.push(temp); } } else if(a[x][y] == ‘|‘) { for(int i = 0;i < 2;i++) { point temp; temp.x = x+dir[i][0]; temp.y = y+dir[i][1]; q.push(temp); } } else { point temp; temp.x = x+dir[1][0]; temp.y = y+dir[1][1]; q.push(temp); } }}void bfs2(point stop){ queue<point> q; q.push(stop); while(!q.empty()) { int x= q.front().x,y = q.front().y; q.pop(); canfrom[x][y] = 1; for(int i = 0;i < 4;i++) { int xx = x+dir[i][0],yy = y+dir[i][1]; if(xx<0 || xx>=r || yy<0 || yy>=c || canfrom[xx][yy]) continue; if(a[xx][yy]==‘S‘ || a[xx][yy]==‘T‘ || a[xx][yy]==‘+‘ || i==0&&a[xx][yy]==‘.‘ || i<=1&&a[xx][yy]==‘|‘ || i>=2&&a[xx][yy]==‘-‘) { point temp; temp.x = xx; temp.y = yy; q.push(temp); } } }}int main(){ scanf("%d%d",&r,&c); getchar(); for(int i = 0;i < r;i++) gets(a[i]); for(int i = 0;i < r;i++) { for(int j = 0;j < c;j++) { if(a[i][j] == ‘S‘) start.x = i,start.y = j; else if(a[i][j] == ‘T‘) stop.x = i,stop.y = j; } } bfs1(start); if(!cango[stop.x][stop.y]) { printf("I‘m stuck!\n"); return 0; } bfs2(stop); int num = 0; for(int i = 0;i < r;i++) { for(int j = 0;j < c;j++) { if(cango[i][j] && !canfrom[i][j]) num++; } } printf("%d\n",num);}
CCF_I’m stuck!_bfs
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。