文章

11

粉丝

152

获赞

9

访问

36.0k

头像
BFS + 枚举中间点
P1104
发布于2022年6月8日 22:28
阅读数 4.3k

一道经典的bfs扩展题目

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <cstring>
#include <cmath>
using namespace std;
#define INF 0x7fffffff
#define N  110

struct node
{
    int x,y;
};

int n,m;
node p[4];
char mpt[N][N];
int vis[N][N][4];
int dir[4][2]={1,0,-1,0,0,1,0,-1};

void bfs(int index)
{
    queue<node> q;
    node now,next;
    now.x=p[index].x;
    now.y=p[index].y;
    q.push(now);
    vis[now.x][now.y][index]=0;
    while(!q.empty())
    {
        now=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            next=now;
            next.x+=dir[i][0];
            next.y+=dir[i][1];
            if(next.x<1 || next.x>n || next.y<1 || next.y>m) continue;
            int tmp=vis[now.x][now.y][index];
            if(mpt[next.x][next.y]=='#') tmp++;
            if(tmp<vis[next.x][next.y][index])
            {
             ...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发