BFS练手题——P4328 [COCI2006-2007#1] Slikar

目录

题目

思路

洪水

刺猬路径

AC代码

原手稿

---

题目

给你一个R?C?的矩阵，这个矩阵由???,?.?(点) ,?D?,?S?,?X?组成，会有洪水从?处涌出，每单位时间都会淹没和其四联通的平地，.(点)表示平地，X?是障碍，不可通行，也不会没淹没，S?是出发点，三只刺猬(?)从这里出发前往庇护所，它们只能在没有被洪水淹没的平地上移动，并且每单位时间只能移动到周围一个四联通的格子，D?表示庇护所，庇护所不会被洪水淹没。

输入第一行两个整数R,C?（R,C≤50?），接下来使这个矩阵。

输出到达庇护所的最短时间，或者输出“KAKTUS”，表示根本不可能到。

1：

3 3
D.*
...
.S.

3

2：

3 3
D.*
...
..S

KAKTUS

3：

3 6
D...*.
.X.X..
....S.

6

这是一道比较不错的bfs题（至少本萌新这么认为），但与普通的又不太一样，因为要考虑洪水问题，所以这里要用到两个bfs，下面是我的思考。

思路

洪水

假定一个洪水“*”，它每个时刻向四周四个方向扩散一格，对流过的格子进行标记，并用一个b[][]来记录留到一个格子所需的最短时间。

要注意主判断的条件，条件比较多，不要写漏了

void bfsflood(int x,int y)
{
? ? memset(arr,false,sizeof(arr));//初始化全为false，表示未被访问
? ? front=rear=1;
? ? b[x][y]=0;
? ? q[1]=(p){x,y,0};
? ? while(front<=rear)
? ? {
? ? ? ? p f=q[front++];//从队列头部元素开始取并赋值给f
? ? ? ? for(int i=0;i<4;i++)
? ? ? ? {
? ? ? ? ? ? int nx=f.x+dx[i];//记录x

????????????int ny=f.y+dy[i];//记录y
? ? ? ? ? ? if(nx<1||ny<1||nx>r||ny>c||arr[nx][ny]||a[nx][ny]==-1||!a[nx][ny])continue;//主判断
? ? ? ? ? ? arr[nx][ny]=true;
? ? ? ? ? ? q[++rear]=(p){nx,ny,f.step+1};//创建一个新的p类型，并初始化成员变量:nx,ny,f.step+1
? ? ? ? ? ? b[nx][ny]=min(b[nx][ny],q[rear].step);//

记录从起点到各个终点的最小值
? ? ? ? }
? ? }
}

刺猬路径

这一段其实与上一段大差不差，都是同一个思路

void bfsroad(int x,int y)
{
? ? memset(arr,false,sizeof(arr));
? ? front=rear=1;
? ? q[1]=(p){x,y,0};
? ? while(front<=rear)
? ? {
? ? ? ? p f=q[front++];
? ? ? ? for(int i=0;i<4;i++)
? ? ? ? {
? ? ? ? ? ? int nx=f.x+dx[i],ny=f.y+dy[i];
? ? ? ? ? ? if(nx<1||ny<1||nx>r||ny>c||arr[nx][ny]||!a[nx][ny]||f.step+1>=b[nx][ny])continue;
? ? ? ? ? ? arr[nx][ny]=true;
? ? ? ? ? ? q[++rear]=(p){nx,ny,f.step+1};
? ? ? ? ? ? if(a[nx][ny]==-1)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? printf("%d",q[rear].step);
? ? ? ? ? ? ? ? exit(0);//强制终止程序(return和break都不行),否则会继续执行下一个cout
? ? ? ? ? ? }?
? ? ? ? }
? ? }cout<<"KAKTUS";
}

AC代码

#include<iostream>
#include<string.h>
using namespace std;
int r,c;
int front,rear,sx,sy;
int a[100][100],b[100][100];
int dx[]={-1,0,0,1};
int dy[]={0,-1,1,0};
bool arr[100][100];
struct p
{
    int x,y,step;
}q[2500];
void bfsflood(int x,int y)
{
    memset(arr,false,sizeof(arr));
    front=rear=1;
    b[x][y]=0;
    q[1]=(p){x,y,0};
    while(front<=rear)
    {
        p f=q[front++];
        for(int i=0;i<4;i++)
        {
            int nx=f.x+dx[i],ny=f.y+dy[i];
            if(nx<1||ny<1||nx>r||ny>c||arr[nx][ny]||a[nx][ny]==-1||!a[nx][ny])continue;
            arr[nx][ny]=true;
            q[++rear]=(p){nx,ny,f.step+1};
            b[nx][ny]=min(b[nx][ny],q[rear].step);
        }
    }
}
void bfsroad(int x,int y)
{
    memset(arr,false,sizeof(arr));
    front=rear=1;
    q[1]=(p){x,y,0};
    while(front<=rear)
    {
        p f=q[front++];
        for(int i=0;i<4;i++)
        {
            int nx=f.x+dx[i],ny=f.y+dy[i];
            if(nx<1||ny<1||nx>r||ny>c||arr[nx][ny]||!a[nx][ny]||f.step+1>=b[nx][ny])continue;
            arr[nx][ny]=true;
            q[++rear]=(p){nx,ny,f.step+1};
            if(a[nx][ny]==-1)
            {
                printf("%d",q[rear].step);
                exit(0);
            } 
        }
    }puts("KAKTUS");
}
int main()
{
  memset(b,1,sizeof(b));
    scanf("%d%d",&r,&c);
    for(int i=1;i<=r;i++)
    {
        for(int j=1;j<=c;j++)
        {
            char c=getchar();
            while(c!='D'&&c!='S'&&c!='X'&&c!='.'&&c!='*')
			c=getchar();
            switch(c)
            {
                case 'S':
                {
                    sx=i;
                    sy=j;
                    break;
                }
                case 'D':
                {
                    a[i][j]=-1;
                    break;
                }
                case 'X':
					break;
                case '*':
                {
                    a[i][j]=2;
                    break;
                }
                case '.':
                {
                    a[i][j]=1;
                    break;
                }
            }
        }
    }
    for(int i=1;i<=r;i++)
    {
        for(int j=1;j<=c;j++)
        {
            if(a[i][j]!=2)
			continue;
            bfsflood(i,j);
        }
    }
    bfsroad(sx,sy);
}

原手稿