首页 > 代码库 > nyist 999 师傅又被妖怪抓走了 【双广搜 || BFS +状态压缩】
nyist 999 师傅又被妖怪抓走了 【双广搜 || BFS +状态压缩】
题目:nyist 999 师傅又被妖怪抓走了
分析:在一个图中只要看到D点和E点就行的最小步数,看到的定义是:也就是说两个人在同一行或者同一列,并且中间没有障碍物或者没有其他人就可以看到对方。
所以可以先预处理地图,把D点和E点所在的行列的‘ .’扩展为d和e,然后只要搜到d和e就可以,问题是只有d和e同时搜到才行,直接广搜肯定不行,我们可以在搜到d点之后然后在从当前点广搜e点,或者e点广搜d点,这样第一次搜到的点不一定是最优的,所以需要枚举所有情况才行,时间复杂度较高。
比较好的一种方法是BFS+状态压缩,定义dp【i】【j】【st】:如果搜到e,状态变化dp【i】【j】【01】,重新初始化图标记,再搜,然后搜到d则dp【i】【j】【10】,知道dp【i】【j】【11】是step就是最小的。这样复杂度较低
双广搜AC代码:
#include <cstdio> #include <cstring> #include <string> #include <iostream> #include <algorithm> #include <queue> #include <vector> using namespace std; #define INT long long #define Del(a,b) memset(a,b,sizeof(a)) const INT inf = 0x3f3f3f3f; const int N = 120; int mp[N][N]; bool vis[N][N],css[N][N]; int n,m,t; int ans; //标记 struct Node { int x,y; int step; }; int dx[5]= {0,0,1,-1}; int dy[5]= {1,-1,0,0}; bool check(int x,int y) { if(mp[x][y]=='X' || mp[x][y]=='D' || mp[x][y]=='E') return false; return true; } char solve(char x,int ok) { if(ok && x=='e' || !ok && x=='d') return 'y'; return ok?'d':'e'; } void isit(int x,int y,int ok) { for(int i=x+1; i<m && check(i,y); i++) mp[i][y]=solve(mp[i][y],ok); for(int i=x-1; i>=0 && check(i,y); i--) mp[i][y] = solve(mp[i][y],ok); for(int j=y+1; j<n && check(x,j); j++) mp[x][j] = solve(mp[x][j],ok); for(int j=y-1; j>=0 && check(x,j); j--) mp[x][j] = solve(mp[x][j],ok); } int BFS2(Node s,int ok) { Del(css,0); queue<Node> f; f.push(s); css[s.x][s.y]=1; while(!f.empty()) { Node x = f.front(),tmp; f.pop(); if(ok && mp[x.x][x.y]=='e' || !ok && mp[x.x][x.y]=='d') return x.step; for(int i=0;i<4;i++) { tmp.x = x.x + dx[i]; tmp.y = x.y + dy[i]; tmp.step = x.step + 1; if(check(tmp.x,tmp.y) && css[tmp.x][tmp.y]==0 && tmp.x>=0 && tmp.y>=0 && tmp.x<n && tmp.y<m) { css[tmp.x][tmp.y]=1; f.push(tmp); } } } return inf; } void BFS(Node s) { s.step = 0; Del(vis,0); queue<Node> q; q.push(s); vis[s.x][s.y]=1; while(!q.empty()) { Node x = q.front(),f; q.pop(); if(mp[x.x][x.y]=='y') ans = min(ans,x.step); else if(mp[x.x][x.y]=='d'){ int fff = BFS2(x,1); ans = min(ans,fff); } else if(mp[x.x][x.y]=='e') { int eee = BFS2(x,0); ans = min(ans,eee); } for(int i=0; i<4; i++) { f.x = x.x + dx[i]; f.y = x.y + dy[i]; f.step = x.step + 1; if(check(f.x,f.y) && vis[f.x][f.y]==0 && f.x>=0 && f.y>=0 && f.x<n && f.y<m) { vis[f.x][f.y]=1; q.push(f); } } } } int main() { int cas=1; while(~scanf("%d%d%d",&n,&m,&t)) { Del(mp,0); //记得初始化 Node s; for(int i=0; i<n; i++) { getchar(); for(int j=0; j<m; j++) { scanf("%c",&mp[i][j]); if(mp[i][j]=='S') s.x=i,s.y=j; } } for(int i=0; i<n; i++) //预处理 { for(int j=0; j<m; j++) { if(mp[i][j]=='D') isit(i,j,1); else if(mp[i][j]=='E') isit(i,j,0); } } ans = inf; BFS(s); printf("Case %d:\n",cas++); if(ans<=t) printf("%d\n",ans); else puts("-1"); } return 0; }
nyist 999 师傅又被妖怪抓走了 【双广搜 || BFS +状态压缩】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。