专栏首页奇妙的算法世界codeforces329B(bfs)

codeforces329B(bfs)

题意描述

给定RxC的网格,网格中存在猎人,询问走到终点前要和多少组猎人碰面

思路

由于猎人事先知道我们行走的路线,所以猎人们可以先走到终点前等待,可以使用bfs预处理出终点到各个点之间的距离,如果猎人到终点的距离小于等于我们从起点到终点的距离,那么一点可以相遇,最后遍历一遍即可。

代码

#include<bits/stdc++.h>
#define x first
#define y second
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<long,long> PLL;
typedef pair<char,char> PCC;
typedef long long LL;
const int N=1010;
const int M=150;
const int INF=0x3f3f3f3f;
const int MOD=998244353;
char g[N][N];
int d[N][N];
int n,m,stx,sty,edx,edy;
int dx[4]={0,1,-1,0},dy[4]={1,0,0,-1};
void bfs(){
    queue<PII> q;
    memset(d,INF,sizeof d);
    d[edx][edy]=0;
    q.push({edx,edy});
    while(q.size()){
        PII t=q.front();q.pop();
        for(int i=0;i<4;i++){
            int gx=t.x+dx[i],gy=t.y+dy[i];
            if(gx>=0 && gy>=0 && gx<n && gy<m && d[gx][gy]==INF && g[gx][gy]!='T'){
                d[gx][gy]=d[t.x][t.y]+1;
                q.push({gx,gy});
            }
        }
    }
}
void solve(){
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>g[i];
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(g[i][j]=='S'){
                stx=i;
                sty=j;
            }
            if(g[i][j]=='E'){
                edx=i;
                edy=j;
            }
        }
    }
    bfs();
    int res=d[stx][sty];
    int ans=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(d[i][j]<=res && g[i][j]>'0' && g[i][j]<='9'){
                ans+=g[i][j]-'0';
            }
        }
    }
    cout<<ans<<endl;
}
int main(){
    IOS;
    solve();
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • codeforces 377A(dfs)

    我们可以反过来想,添k堵墙可以想成给cnt-k个空地构成的连通块打上标记,没有打上标记的即为空地

    dejavu1zz
  • codeforces 429A(dfs)

    给定一棵树,树的每个结点上有一个值,你可以对树上的值进行异或操作,求使树上的结点值成为目标值所需的最少操作

    dejavu1zz
  • SCU2511(单调栈)

    我们维护一个单调递减栈,使用一个数组来记录第i只牛所能听到的噪音,最后求最大值即可

    dejavu1zz
  • OpenCV图像处理专栏十 | 利用中值滤波进行去雾

    这是OpenCV图像处理专栏的第十篇文章,介绍一种利用中值滤波来实现去雾的算法。这个方法发表于国内的一篇论文,链接我放附录了。

    BBuf
  • LeetCode 323. 无向图中连通分量的数目(并查集)

    给定编号从 0 到 n-1 的 n 个节点和一个无向边列表(每条边都是一对节点),请编写一个函数来计算无向图中连通分量的数目。

    Michael阿明
  • BZOJ3143: [Hnoi2013]游走(期望DP 高斯消元)

    Description 一个无向连通图,顶点从1编号到N,边从1编号到M。  小Z在该图上进行随机游走,初始时小Z在1号顶点,每一步小Z以相等的概率随机选 择当...

    attack
  • 2017.5.20欢(bei)乐(ju)赛解题报告

    预计分数:100+20+50=first 实际分数:20+0+10=gg 水灾(sliker.cpp/c/pas) 1000MS  64MB 大雨应经下了几天雨...

    attack
  • 树上莫队算法

    attack
  • 挑战程序竞赛系列(23):3.2折半枚举

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • BZOJ2535: [Noi2010]Plane 航空管制2(拓扑排序 贪心)

    首先不难想到拓扑排序,但是直接对原图按\(k\)从小到大拓扑排序是错的。因为当前的\(k\)大并不意味着后面的点\(k\)也大

    attack

扫码关注云+社区

领取腾讯云代金券