题解 P1301 【魔鬼之城】

· · 题解

这道题在蒟蒻看来就是bfs的模板，但是还是有一个坑点。

主要是visit数组，本蒟蒻在10分卡了很久，就是因为visit数组没有开三维。

v[i][j][way]表示第i行第j列是其他点走way这个方向走来的。

还有v数组应保存从任一点走到这里的最小步数。

请大家看我题解中c++代码中最短的一篇

CODE:

#include<bits/stdc++.h>
using namespace std;
int mapa[105][105];
int v[105][105][10];
int dx[9]={0,0,1,1,1,0,-1,-1,-1};
int dy[9]={0,-1,-1,0,1,1,1,0,-1};
struct node{
    int x,y,step,way;
};
queue<node> q;
int main()
{
    int n,m;
    memset(v,0,sizeof(v));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&mapa[i][j]);
    node start;
    start.x=1,start.y=1;
    start.step=0,start.way=9;
    q.push(start);
    while(!q.empty())
    {
        node now=q.front();
        q.pop();
        if(now.x==m&&now.y==n)
        {
            printf("%d",now.step);
            return 0;
        }
        for(int i=1;i<=8;i++)
        {
            if(now.way!=i)
            {
                int tx=now.x+dx[i]*mapa[now.x][now.y];
                int ty=now.y+dy[i]*mapa[now.x][now.y];
                int ts=now.step;
                if(tx<=m&&ty<=n&&tx>=1&&ty>=1&&v[tx][ty][i]==0)
                {
                    v[tx][ty][i]=1;
                    node ans;
                    ans.x=tx,ans.y=ty;
                    ans.step=ts+1,ans.way=i;
                    q.push(ans);
                }
            }
        }
    }
    printf("NEVER");
}

在此，特别鸣谢jackyzhu教蒟蒻做题。