题解 P5195 【[USACO05DEC]Knights of Ni】

· · 题解

我被这道题坑了很久（现在感觉不难了）

仔细康康你会发现这其实就是道简单的广搜（我不会最短路径算法）

但是我最后发现好像并不要专门剪枝，只要你别想太多就行；

要注意的点：

  1. 搜两边，一遍从贝茜开始（不能经过骑士的位置），另一遍从骑士的位置开始（除了障碍都能走）；

  2. 搜索的时候要把所有灌木丛都找到最短路；

  3. 搜索到一个灌木丛要标记成路（一开始标记成障碍了 [哭] ），但是在第二次搜索前要恢复（这个我一开始也忘了[哭*2]）；

  4. 恢复方法最好是输入时标记好灌木丛的位置，到时候直接枚举每一丛的位置就行

  5. 标记灌木丛位置用的结构体（数组）开大一点！！！你永远不知道出题人在那里放了多少丛灌木（我RE了）

最后温馨提示 >▽<：找到灌木丛后别忘了continue( RE警告 )

然后上代码：

#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
int m,n,sx,sy,ex,ey;
int dx[5]={0,-1,1,0,0};
int dy[5]={0,0,0,-1,1};
int a[1010][1010];
long long ji;
struct lol
{
    int x1,y1;
}guan_mu_cong[10000];
bool b[1010][1010];
long long ji1[1010][1010],ji2[1010][1010];
struct node
{
    int x,y,tim;
}qwq;
long long minn=0x7f7f7f7f;
queue<node>q;
int main()
{
    cin>>m>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
            if(a[i][j]==2)
            {
                sx=i;
                sy=j;
            }
            else if(a[i][j]==3)
            {
                ex=i;
                ey=j;
            }
            else if(a[i][j]==4)
            {
                guan_mu_cong[++ji].x1=i;
                guan_mu_cong[ji].y1=j;
            }
        }
    }
    qwq.x=sx;
    qwq.y=sy;
    qwq.tim=0;
    q.push(qwq);
    while(!q.empty())
    {
        qwq=q.front();
        if(a[qwq.x][qwq.y]==4&&ji1[qwq.x][qwq.y]==0)
        {
            ji1[qwq.x][qwq.y]=qwq.tim;
            a[qwq.x][qwq.y]=0;
            q.pop();
            continue;
        }
        for(int i=1;i<=4;i++)
        {
            qwq=q.front();
            qwq.x+=dx[i];
            qwq.y+=dy[i];
            qwq.tim++;
            if(qwq.x>0&&qwq.x<=n&&qwq.y>0&&qwq.y<=m&&(a[qwq.x][qwq.y]==0||a[qwq.x][qwq.y]==4)&&b[qwq.x][qwq.y]==0)
            {
                q.push(qwq);
                b[qwq.x][qwq.y]=1;
            }
        }
        q.pop();
    }
    while(!q.empty())
    {
        q.pop();
    }
    for(int i=1;i<=ji;i++)
    a[guan_mu_cong[i].x1][guan_mu_cong[i].y1]=4;
    qwq.tim=0;
    qwq.x=ex;
    qwq.y=ey;
    q.push(qwq);
    memset(b,0,sizeof(b));
    while(!q.empty())
    {
        qwq=q.front();
        if(a[qwq.x][qwq.y]==4&&ji2[qwq.x][qwq.y]==0)
        {
            ji2[qwq.x][qwq.y]=qwq.tim;
            a[qwq.x][qwq.y]=0;
            q.pop();
            continue;
        }
        for(int i=1;i<=4;i++)
        {
            qwq=q.front();
            qwq.x+=dx[i];
            qwq.y+=dy[i];
            qwq.tim++;
            if(qwq.x>0&&qwq.x<=n&&qwq.y>0&&qwq.y<=m&&(a[qwq.x][qwq.y]!=1)&&b[qwq.x][qwq.y]==0)
            {
                q.push(qwq);
                b[qwq.x][qwq.y]=1;
            }
        }
        q.pop();
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(ji1[i][j]&&ji2[i][j])
            minn=min(minn,ji1[i][j]+ji2[i][j]);
        }   
    }
    cout<<minn;
}

代码长也就100来行

祝各位dalao轻松AC这道水题