百练 4116 拯救行动(bfs)

2024-02-10 07:32
文章标签 bfs 拯救 行动 百练 4116

本文主要是介绍百练 4116 拯救行动(bfs)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

描述

公主被恶人抓走，被关押在牢房的某个地方。牢房用N*M (N, M <= 200)的矩阵来表示。矩阵中的每项可以代表道路（@）、墙壁（#）、和守卫（x）。
英勇的骑士（r）决定孤身一人去拯救公主（a）。我们假设拯救成功的表示是“骑士到达了公主所在的位置”。由于在通往公主所在位置的道路中可能遇到守卫，骑士一旦遇到守卫，必须杀死守卫才能继续前进。
现假设骑士可以向上、下、左、右四个方向移动，每移动一个位置需要1个单位时间，杀死一个守卫需要花费额外的1个单位时间。同时假设骑士足够强壮，有能力杀死所有的守卫。给定牢房矩阵，公主、骑士和守卫在矩阵中的位置，请你计算拯救行动成功需要花费最短时间。

输入
第一行为一个整数S，表示输入的数据的组数（多组输入）
随后有S组数据，每组数据按如下格式输入
1、两个整数代表N和M, (N, M <= 200).
2、随后N行，每行有M个字符。”@”代表道路，”a”代表公主，”r”代表骑士，”x”代表守卫, “#”代表墙壁。
输出
如果拯救行动成功，输出一个整数，表示行动的最短时间。
如果不可能成功，输出”Impossible”
样例输入

2
7 8
#@#####@
#@a#@@r@
#@@#x@@@
@@#@@#@#
#@@@##@@
@#@@@@@@
@@@@@@@@ 
13 40
@x@@##x@#x@x#xxxx##@#x@x@@#x#@#x#@@x@#@x
xx###x@x#@@##xx@@@#@x@@#x@xxx@@#x@#x@@x@
#@x#@x#x#@@##@@x#@xx#xxx@@x##@@@#@x@@x@x
@##x@@@x#xx#@@#xxxx#@@x@x@#@x@@@x@#@#x@#
@#xxxxx##@@x##x@xxx@@#x@x####@@@x#x##@#@
#xxx#@#x##xxxx@@#xx@@@x@xxx#@#xxx@x#####
#x@xxxx#@x@@@@##@x#xx#xxx@#xx#@#####x#@x
xx##@#@x##x##x#@x#@a#xx@##@#@##xx@#@@x@x
x#x#@x@#x#@##@xrx@x#xxxx@##x##xx#@#x@xx@
#x@@#@###x##x@x#@@#@@x@x@@xx@@@@##@@x@@x
x#xx@x###@xxx#@#x#@@###@#@##@x#@x@#@@#@@
#@#x@x#x#x###@x@@xxx####x@x##@x####xx#@x
#x#@x#x######@@#x@#xxxx#xx@@@#xx#x#####@

样例输出

13
7

思路
这道题用普通bfs可以过样例,但是提交过不了,这道题是看了别人代码做的,
有两种方法.
一种是用priority_queue 做（暂时不太懂）
另一种方法是拆点
拆点就是对于 ‘x’ ，它的扩展要分两次：
对于(‘x’,0) ，它只能扩展出 ( ‘x’ , 1 )
对于(‘x’,1) , 它可以往四个方向扩展.
第一种 priority_queue

/*************************************************************************> File Name: bl4116.cpp> Author:ukiy > Mail: > Created Time: 2016年12月03日 星期六 22时34分06秒************************************************************************/#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<string>
#include<cstring>
#include<vector>
#include<set>
#include<list>
#include<map>
#include<queue>
int dire[4][2]={ {0,1},{1,0},{0,-1},{-1,0} };
int dire2[8][2]={{-1,-1},{-1,0},{-1,1},{ 0,-1},{ 0,1},{ 1,-1},{ 1,0},{ 1,1}};
#define rep(i,a,b) for(int i=(a);i<=(b);(i++))
#define inf 0x3f3f3f
#define ll long long
#define pi acos(-1)
int dire3[6][3]={ {0,0,1},{0,1,0},{1,0,0},{0,0,-1},{0,-1,0},{-1,0,0} };
using namespace std;
const int maxn=205;
int visit[maxn][maxn];
char a[maxn][maxn];
int n,m;
int sx,sy,dx,dy;
struct node{int x,y,step;bool operator < (const node& p) const {  return step>p.step;  } node(int xx,int yy,int s):x(xx),y(yy),step(s){};
};int  bfs(int x,int y){priority_queue<node> q;q.push(node(x,y,0));visit[x][y]=1;while(!q.empty()){int hx=q.top().x,hy=q.top().y,hs=q.top().step;q.pop();if(hx==dx && hy==dy)  return hs;rep(i,0,3){int tx=hx+dire[i][0];int ty=hy+dire[i][1];if(tx<0||tx>=n||ty<0||ty>=m||a[tx][ty]=='#'||visit[tx][ty])continue;if(a[tx][ty]=='x') q.push(node(tx,ty,hs+2));else q.push(node(tx,ty,hs+1));visit[tx][ty]=1;}}return -1;
}
/*
int bfs(){int front=0;int rear=1;q[front].x=sx,q[front].y=sy,q[front].step=0;visit[sx][sy]=1;int flag=0;while(front < rear){if(q[front].x==dx && q[front].y==dy) return q[front].step;rep(i,0,3){int px=q[front].x+dire[i][0];int py=q[front].y+dire[i][1];if(px<0||px>=n||py<0||py>=m||visit[px][py]||a[px][py]=='#')continue;else{q[rear].x=px;q[rear].y=py;if(a[px][py]=='@'||a[px][py]=='a')q[rear].step=q[front].step+1;else if(a[px][py]=='x')q[rear].step=q[front].step+2;visit[px][py]=1;rear++;}} front++;}return -1;
}
*/
int main()
{std::ios::sync_with_stdio(false);#ifndef OnlineJudge//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);#endifint t;cin>>t;while(t--){cin>>n>>m;rep(i,0,n-1){rep(j,0,m-1){cin>>a[i][j];if(a[i][j]=='r') sx=i,sy=j;if(a[i][j]=='a') dx=i,dy=j;}}memset(visit,0,sizeof(visit));int ans=bfs(sx,sy);if(ans==-1) printf("Impossible\n");  else printf("%d\n",ans);}return 0;
}

第二种 拆点

/*************************************************************************
    > File Name: bl4116_2.cpp
    > Author:ukiy 
    > Mail: 
    > Created Time: 2016年12月04日 星期日 01时19分50秒************************************************************************/#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<string>
#include<cstring>
#include<vector>
#include<set>
#include<list>
#include<map>
#include<queue>
int dire[4][2]={ {0,1},{1,0},{0,-1},{-1,0} };
int dire2[8][2]={{-1,-1},{-1,0},{-1,1},{ 0,-1},{ 0,1},{ 1,-1},{ 1,0},{ 1,1}};
#define rep(i,a,b) for(int i=(a);i<=(b);(i++))
#define inf 0x3f3f3f
#define ll long long
#define pi acos(-1)
int dire3[6][3]={ {0,0,1},{0,1,0},{1,0,0},{0,0,-1},{0,-1,0},{-1,0,0} };
using namespace std;
#define maxn 205
struct node{
    int r,c,t;
    node (int r,int c,int t):r(r),c(c),t(t){}
};char g[maxn][maxn];
int G[maxn][maxn];
int  vis[maxn][maxn];
int sx,sy,dx,dy;
int n,m;
int bfs(){
    int ans=inf;
    queue<node> q;
    q.push(node(sx,sy,0));
    while(!q.empty()){
        node p = q.front();
        if(g[p.r][p.c]=='a'){
            ans=min(ans,p.t);
            q.pop();
            break;
        }        if(g[p.r][p.c]=='x'&&G[p.r][p.c]==1){ //第二次拆点
            q.push(node(p.r,p.c,p.t+1));
            G[p.r][p.c]=0;
        }
        else{
            rep(i,0,3){
                int tr=p.r+dire[i][0];
                int tc=p.c+dire[i][1];
                if(tr>=0&&tr<n&&tc>=0&&tc<m && G[tr][tc]){
                    if(g[tr][tc]!='x'){
                        q.push(node(tr,tc,p.t+1));
                        G[tr][tc]=0;
                    }
                    if(g[tr][tc]=='x'&&G[tr][tc]==2){//第一次拆点 
                        q.push(node(tr,tc,p.t+1));
                        G[tr][tc]=1;
                    }
                }
            }
        }
        q.pop();
    }
    if(ans==inf)
        return -1;
    else
        return ans;
}int main()
{
    std::ios::sync_with_stdio(false);
    #ifndef OnlineJudge
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    #endif
    int T;
    cin>>T;
    while(T--){
        cin>>n>>m;
        rep(i,0,n-1){
            rep(j,0,m-1){
                cin>>g[i][j];
                if(g[i][j]=='x') G[i][j]=2;
                else if(g[i][j]=='@'||g[i][j]=='a') G[i][j]=1;
                else if(g[i][j]=='r') G[i][j]=0,sx=i,sy=j;
                else G[i][j]=0;
            }
        }
        //memset(G,0,sizeof(G));
        int ans=bfs();
        if(ans==-1) printf("Impossible\n");
        else  printf("%d\n",ans);
    }
    return 0;
}

priority_queue 原文
BRCOCOLI http://blog.csdn.net/qq_34446253/article/details/51986930

拆点 原文
appledaily http://blog.csdn.net/hhhhhhj123/article/details/47070659

这篇关于百练 4116 拯救行动(bfs)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/696506。

相关文章

hdu1254（嵌套bfs，两次bfs）

hdu1254（嵌套bfs，两次bfs）

/*第一次做这种题感觉很有压力，思路还是有点混乱，总是wa，改了好多次才ac的思路：把箱子的移动当做第一层bfs，队列节点要用到当前箱子坐标（x，y），走的次数step，当前人的weizhi（man_x，man_y），要判断人能否将箱子推到某点时要嵌套第二层bfs（人的移动）；代码如下：
阅读更多...
poj 2195 bfs+有流量限制的最小费用流

poj 2195 bfs+有流量限制的最小费用流

题意： 给一张n * m（100 * 100）的图，图中” . " 代表空地， “ M ” 代表人， “ H ” 代表家。 现在，要你安排每个人从他所在的地方移动到家里，每移动一格的消耗是1，求最小的消耗。 人可以移动到家的那一格但是不进去。 解析： 先用bfs搞出每个M与每个H的距离。 然后就是网络流的建图过程了，先抽象出源点s和汇点t。 令源点与每个人相连，容量为1，费用为
阅读更多...
POJ 3057 最大二分匹配+bfs + 二分

POJ 3057 最大二分匹配+bfs + 二分

SampleInput35 5XXDXXX...XD...XX...DXXXXX5 12XXXXXXXXXXXXX..........DX.XXXXXXXXXXX..........XXXXXXXXXXXXX5 5XDXXXX.X.DXX.XXD.X.XXXXDXSampleOutput321impossible
阅读更多...
深度优先（DFS）和广度优先（BFS）——算法

深度优先（DFS）和广度优先（BFS）——算法

深度优先 深度优先搜索算法（英语：Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点，尽可能深的搜索树的分支，当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访
阅读更多...
双头BFS

双头BFS

牛客月赛100 D题，过了80%数据，调了一下午。。。烦死了。。。 还是没调试出来，别人的代码用5维的距离的更新有滞后性，要在遍历之前要去重。。。 #include<bits/stdc++.h>using namespace std;const int N=2e3+10;char g[N][N];int dis[N][N],d1[N][N];int n,m,sx,sy;int dx
阅读更多...
Knight Moves -uva 简单的BFS遍历

Knight Moves -uva 简单的BFS遍历

昨天刚学了BFS的遍历，在uva上找了个题敲了出来，感觉还不错，最近敲代码挺有手感的，希望这种状态保持下去 #include<iostream>#include<stdio.h>#include<stdlib.h>#include<string.h>#define MAX_SIZE 10 + 5#define LEN 100 + 10using namespace std;in
阅读更多...
【CF】D. Arthur and Walls（BFS + 贪心）

【CF】D. Arthur and Walls（BFS + 贪心）

D题 解题思路就是每次检查2X2的方格里是否只有一个‘*’，如果有的话这个*就需要变成‘.’，利用BFS进行遍历，入队的要求是这个点为. 一开始将所有的'.'全部加入队列，如果碰到一个'*'变成'.'就入队，判断的时候从4个方向就行判断 题目链接：http://codeforces.com/contest/525/problem/D #include<cstdio>#include<
阅读更多...
hdu2717(裸bfs广搜)

hdu2717(裸bfs广搜)

Catch That Cow Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 7304 Accepted Submission(s): 2308 题目链接： http://acm.hdu.edu.cn/showproblem.
阅读更多...
Codeforces#295(Div.2)A、B(模拟+BFS)

Codeforces#295(Div.2)A、B(模拟+BFS)

解题报告链接：点击打开链接 C. 题目链接：点击打开链接 解题思路： 对于给定的字符串，取出现次数最多的字母（可以同时有多个）。由这些字母组成长度为n的字符串，求有多少种组合。最后用数学知识即可。 完整代码： #include <algorithm>#include <iostream>#include <cstring>#include <climits>
阅读更多...
java常用算法之字梯（广度优先搜索bfs）

java常用算法之字梯（广度优先搜索bfs）

<span style="font-family: 'microsoft yahei', simhei, arial, sans-serif; font-size: 16px;">给定2个单词（start</span><span style="font-family: 'microsoft yahei', simhei, arial, sans-serif; font-size: 16px;">和
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2