portal

[编程题]portal

热度指数：60 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛牛最近完了一款名叫传送门的游戏，但是他不满足于只是通关，他希望找到每一关的最佳通关方式。

游戏是在一个N*N的网格图中进行的，图中的网格分为四种类型，0表示空地可以通过，1表示墙壁无法通过，2表示不仅可以通过，还可以在该格放置一个传送门，3表示有且仅有的唯一的固定传送门。

在游戏开始时，牛牛可以选择一块2类型的格子放置传送门并且不可以中途更改，在游戏过程中，如果到达其中一个传送门，则可以传送往另一个传送门。游戏的起点始终为左上角，终点始终为右下角，牛牛每次可以往四个方向移动，即上下左右四个方向。牛牛想知道从起点走到终点最少需要走几步（使用传送门也算作一步）。

返回：最少的需要走的步数。

示例1

输入

6,[[0,0,3,0,0,0],[0,0,0,2,2,0],[1,1,1,2,1,0],[2,1,0,0,0,0],[0,0,0,0,0,1],[0,1,1,1,0,0]]

输出

备注:

保证地图中有且仅有一个标为3的格子，不保证一定有标为2的格子。
无论是否放置传送门，标为3的格子和标为2的格子都可以正常通过。
保证一定存在可行方案。
样例的直观图为:
0 0 3 0 0 0
0 0 0 2 2 0
1 1 1 2 1 0
2 1 0 0 0 0
0 0 0 0 0 1
0 1 1 1 0 0

算法知识视频讲解

牛客978235905号

先刷基础路径，再考虑传送门

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最终要输出的答案
     * @param N int整型 表示地图的大小
     * @param a int整型vector<vector<>> 地图的描述
     * @return int整型
     */
    int c3c=-1;
    int c2c=-1;
    int w3c=-1;
    int w2c=-1;
    int b1[500][500];
    int b2[500][500];
    int solve(int N, vector<vector<int> >& a) 
    {
        // write code here
        //vector<vector<int> > c;
        int jg1;
        int jg2;
        int jg3;
        int c[500][2];
        int cc=1;
        int c4=1;
        int lc=0;
        c[0][0]=0;
        c[0][1]=0;
        lc=lc+1;
        for(int x1=0;x1<N;x1++)
        {
            for(int x2=0;x2<N;x2++)
            {
                b1[x1][x2]=0; 
                b2[x1][x2]=0; 
            }
        }
        while(b1[N-1][N-1]==0)
        {
        int c1s=0;
        int cc1=0;
        int c1[500][2];
        for(int i1=0;i1<cc ;i1++)
        {
            if(c[i1][0]>0 && a[c[i1][0]-1][c[i1][1]]!=1 && b1[c[i1][0]-1][c[i1][1]]==0)
            {
                cc1++;
                b1[c[i1][0]-1][c[i1][1]]=lc;
                c1[c1s][0]=c[i1][0]-1;
                c1[c1s][1]=c[i1][1];
                c1s++;
                if(a[c[i1][0]-1][c[i1][1]]==3)
                {
                    c3c=lc;
                }
                if(a[c[i1][0]-1][c[i1][1]]==2 && c2c==-1)
                {
                    c2c=lc;
                }
            }
            if(c[i1][1]>0 && a[c[i1][0]][c[i1][1]-1]!=1 && b1[c[i1][0]][c[i1][1]-1]==0)
            {
                cc1++;
                b1[c[i1][0]][c[i1][1]-1]=lc;
                c1[c1s][0]=c[i1][0];
                c1[c1s][1]=c[i1][1]-1;
                c1s++;
                if(a[c[i1][0]][c[i1][1]-1]==3)
                {
                    c3c=lc;
                }
                if(a[c[i1][0]][c[i1][1]-1]==2 && c2c==-1)
                {
                    c2c=lc;
                }
            }
            if(c[i1][0]<(int(a.size())-1) && a[c[i1][0]+1][c[i1][1]]!=1 && b1[c[i1][0]+1][c[i1][1]]==0)
            {
                cc1++;
                b1[c[i1][0]+1][c[i1][1]]=lc;
                c1[c1s][0]=c[i1][0]+1;
                c1[c1s][1]=c[i1][1];
                c1s++;
                if(a[c[i1][0]+1][c[i1][1]]==3)
                {
                    c3c=lc;
                }
                if(a[c[i1][0]+1][c[i1][1]]==2 && c2c==-1)
                {
                    c2c=lc;
                }
            }
            if(c[i1][1]<(int(a.size())-1) && a[c[i1][0]][c[i1][1]+1]!=1 && b1[c[i1][0]][c[i1][1]+1]==0)
            {
                cc1++;
                b1[c[i1][0]][c[i1][1]+1]=lc;
                c1[c1s][0]=c[i1][0];
                c1[c1s][1]=c[i1][1]+1;
                c1s++;
                if(a[c[i1][0]][c[i1][1]+1]==3)
                {
                    c3c=lc;
                }
                if(a[c[i1][0]][c[i1][1]+1]==2 && c2c==-1)
                {
                    c2c=lc;
                }
            }
        }
            for(int x1=0;x1<cc1;x1++)
            {
                c[x1][0]=c1[x1][0];
                c[x1][1]=c1[x1][1];
            }
            cc=cc1;
        lc=lc+1;
        }
        cc=1;
        c4=1;
        lc=0;
        c[N-1][0]=0;
        c[N-1][1]=0;
        lc=lc+1;
        while((w3c==-1 || w2c==-1) && b2[0][0] == 0)
        {
            
            int c1s=0;
            int cc1=0;
            int c1[500][2];
                    for(int i1=0;i1<cc ;i1++)
        {
            if(c[i1][0]>0 && a[c[i1][0]-1][c[i1][1]]!=1 && b2[c[i1][0]-1][c[i1][1]]==0)
            {
                cc1++;
                b2[c[i1][0]-1][c[i1][1]]=lc;
                c1[c1s][0]=c[i1][0]-1;
                c1[c1s][1]=c[i1][1];
                c1s++;
                if(a[c[i1][0]-1][c[i1][1]]==3)
                {
                    w3c=lc;
                }
                if(a[c[i1][0]-1][c[i1][1]]==2 && w2c==-1)
                {
                    w2c=lc;
                }
            }
            if(c[i1][1]>0 && a[c[i1][0]][c[i1][1]-1]!=1 && b2[c[i1][0]][c[i1][1]-1]==0)
            {
                cc1++;
                b2[c[i1][0]][c[i1][1]-1]=lc;
                c1[c1s][0]=c[i1][0];
                c1[c1s][1]=c[i1][1]-1;
                c1s++;
                if(a[c[i1][0]][c[i1][1]-1]==3)
                {
                    w3c=lc;
                }
                if(a[c[i1][0]][c[i1][1]-1]==2 && w2c==-1)
                {
                    w2c=lc;
                }
            }
            if(c[i1][0]<(int(a.size())-1) && a[c[i1][0]+1][c[i1][1]]!=1 && b2[c[i1][0]+1][c[i1][1]]==0)
            {
                cc1++;
                b2[c[i1][0]+1][c[i1][1]]=lc;
                c1[c1s][0]=c[i1][0]+1;
                c1[c1s][1]=c[i1][1];
                c1s++;
                if(a[c[i1][0]+1][c[i1][1]]==3)
                {
                    w3c=lc;
                }
                if(a[c[i1][0]+1][c[i1][1]]==2 && w2c==-1)
                {
                    w2c=lc;
                }
            }
            if(c[i1][1]<(int(a.size())-1) && a[c[i1][0]][c[i1][1]+1]!=1 && b2[c[i1][0]][c[i1][1]+1]==0)
            {
                cc1++;
                b2[c[i1][0]][c[i1][1]+1]=lc;
                c1[c1s][0]=c[i1][0];
                c1[c1s][1]=c[i1][1]+1;
                c1s++;
                if(a[c[i1][0]][c[i1][1]+1]==3)
                {
                    w3c=lc;
                }
                if(a[c[i1][0]][c[i1][1]+1]==2 && w2c==-1)
                {
                    w2c=lc;
                }
            }
        }
            for(int x1=0;x1<cc1;x1++)
            {
                c[x1][0]=c1[x1][0];
                c[x1][1]=c1[x1][1];
            }
            cc=cc1;
             lc=lc+1;
            
        }
        jg1 = b1[N-1][N-1];
        jg2=jg1+1;
        jg3=jg1+1;
        if(c2c!=-1 && w3c !=-1)
        {
            jg2 = c2c+w3c+1;
        }
        if(c3c!=-1 && w2c!=-1)
        {
            jg3 = c3c+w2c+1;
        }
        
        if(jg1<=jg2 && jg1 <=jg3)
        {
            return jg1;
        }
        if(jg2<=jg1 && jg2 <=jg3)
        {
            return jg2;
        }
        if(jg3<=jg2 && jg3 <=jg1)
        {
            return jg3;
        }
        return -1;

    }
};

发表于 2021-04-04 19:12:50 回复(0)