首页 > 代码库 > HDU 1242 Rescue
HDU 1242 Rescue
bfs问题。
Angel有被关在监狱,她有很多朋友要去救她。
#表示墙,.表示路,x表示警卫,r表示她的朋友。
由于可能有很多朋友,但是Angel只有一个,所以搜索起点设为Angel。只要找到一个朋友表示能走出去。
走一格需要1,杀死警卫需要1,但是不能直接加2.
因为会出现这种情况
4 8 axxxxxxr ........ ........ ........
如果直接加2的话,答案就不是9.
#include<cstdio> #include<cstring> #include<string> #include<queue> #include<algorithm> #include<map> #include<stack> #include<iostream> #include<list> #include<set> #include<vector> #include<cmath> #define INF 0x7fffffff #define eps 1e-8 #define LL long long #define PI 3.141592654 #define CLR(a,b) memset(a,b,sizeof(a)) #define FOR(i,a,n) for(int i= a;i< n ;i++) #define debug puts("==fuck==") #define acfun std::ios::sync_with_stdio(false) #define SIZE 1000+10 using namespace std; int xx[]={0,0,-1,1}; int yy[]={-1,1,0,0}; int n,m; char g[201][201]; struct lx { int x,y,lv; void init(int xx,int yy,int llv) { x=xx,y=yy,lv=llv; } }; lx start,thend; void bfs() { queue<lx>q; bool vis[201][201]; CLR(vis,0); q.push(start); vis[start.x][start.y]=1; while(!q.empty()) { lx tmp=q.front(); q.pop(); // printf("%d %d == %d\n",tmp.x,tmp.y,tmp.lv); // system("pause"); if(g[tmp.x][tmp.y]=='r') { printf("%d\n",tmp.lv); return ; } FOR(k,0,4) { int x=tmp.x+xx[k]; int y=tmp.y+yy[k]; if(x<0||y<0||x>=n||y>=m||g[x][y]=='#'||vis[x][y]) continue; lx now; if(g[x][y]=='x') { now.init(tmp.x,tmp.y,tmp.lv+1); g[x][y]='.'; } else { now.init(x,y,tmp.lv+1); vis[x][y]=1; } q.push(now); } } puts("Poor ANGEL has to stay in the prison all his life."); } int main() { while(~scanf("%d%d",&n,&m)) { char str[201]; FOR(i,0,n) { scanf("%s",str); FOR(j,0,m) { g[i][j]=str[j]; if(g[i][j]=='a') start.init(i,j,0); } } bfs(); } }
HDU 1242 Rescue
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。