牛客网算法编程题--办公室路径走法 解答

办公室路径走法

题目描述

shopee的办公室非常大,小虾同学的位置坐落在右上角,而大门却在左下角,可以把所有位置抽象为一个网格(门口的坐标为0,0),小虾同学很聪明,每次只向上,或者向右走,因为这样最容易接近目的地,但是小虾同学不想让自己的boss们看到自己经常在他们面前出没,或者迟到被发现。他决定研究一下如果他不通过boss们的位置,他可以有多少种走法?

第一行 x,y,n (0<x<=30, 0<y<=30, 0<=n<= 20) 表示x,y小虾的座位坐标,n 表示boss的数量( n <= 20)

接下来有n行, 表示boss们的坐标(0<xi<= x, 0<yi<=y,不会和小虾位置重合)

x1, y1

x2, y2

……

xn, yn

输入

复制

3 3 2
1 1
2 2

输出

复制

4

方法一:递归遍历(时间复杂度太高,很多点走了多次,sub-problem)

思路:使用自己编写的Point或者awt包下的把点封装成对象,对起始点进行递归,递归的出口为现在所在的点nowPoint为终点或者上面和右边同时存在boss,否则如果右边为空上面不为空,nowPoint往右遍历;如果右边不为空,上边为空则遍历nowPoint上边,如果都为空,对上边和右边同时遍历,最后进行计数并输出.

但是递归时间复杂度太高,可达O(2^n^) 所以牛客网没有通过,它应该是想让我们使用dp(动态规划法)

private static Point endPoint;
    private static List<Point> bossList = new ArrayList<>();
    private static int count = 0;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] s = scanner.nextLine().split(" ");
        endPoint =  new Point(Integer.parseInt(s[0]),Integer.parseInt(s[1]));
        int numberBoss = Integer.parseInt(s[2]);
        for(int i=0;i<numberBoss;i++){
            String[] boss = scanner.nextLine().split(" ");
            bossList.add(new Point(Integer.parseInt(boss[0]),Integer.parseInt(boss[1])));
        }
        Point nowPoint = new Point(0,0);
        walk(nowPoint);
        System.out.println(count);
    }
    private static void walk(Point nowPoint){
        if((nowPoint.x<=endPoint.x&&nowPoint.y<=endPoint.y)
                &&!(nowPoint.x==endPoint.x&&nowPoint.y==endPoint.y)
                &&!(existRight(nowPoint)&&existTop(nowPoint))){
            if(existRight(nowPoint)&&!existTop(nowPoint)){
                nowPoint.translate(0,1);
                walk(nowPoint);
            }else if(existTop(nowPoint)&&!existRight(nowPoint)){
                nowPoint.translate(1,0);
                walk(nowPoint);
            }else if(!existRight(nowPoint)&&!existTop(nowPoint)){
                walk(new Point(nowPoint.x+1,nowPoint.y));
                walk(new Point(nowPoint.x,nowPoint.y+1));
            }
            if(arrive(nowPoint)){
                count++;
            }
        }
    }
    private static boolean existRight(Point nowPoint){
        return bossList.contains(new Point(nowPoint.x+1,nowPoint.y));
    }
    private static boolean existTop(Point nowPoint){
        return bossList.contains(new Point(nowPoint.x,nowPoint.y+1));
    }
    private static boolean arrive(Point nowPoint){
         return (nowPoint.x==endPoint.x&&nowPoint.y==endPoint.y-1)||(nowPoint.x==endPoint.x-1&&nowPoint.y==endPoint.y);
        //return nowPoint.x==endPoint.x&&nowPoint.y==endPoint.y;
    }

方法二:动态规划(把已经走过的点的值保存在数组里)

思路:

使用二维数组保存各点的走法,把有boss的格子赋值为-1,代表走不了,把起始位置的行和列(第0行,第0列)中没有boss的格子赋值为1,代表这些位置可以由初始位置通过一条路径到达(boss后面的除外),这里当然也可以把第一个boss前面的赋值为1;

然后遍历并计算每个格子的值(即为达到该点有几条路径),在进行路径相加时,由于我们把boss设置为了-1,所以应该在检查到boss要被加上时,把它去掉,也就是加上0(不能通过boss这个格子到达),最后得到终点的值也就是最后我们的总路径数.

public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] s = scanner.nextLine().split(" ");
        long[][] dp = new long[Integer.parseInt(s[0])+1][Integer.parseInt(s[1])+1];
        int numberBoss = Integer.parseInt(s[2]);
        for(int i=0;i<numberBoss;i++){
            String[] boss = scanner.nextLine().split(" ");
            dp[Integer.parseInt(boss[0])][Integer.parseInt(boss[1])] = -1;
        }
        System.out.println(count(dp));
    }
    private static long count(long[][] dp) {
        int i = dp.length;
        int j = dp[0].length;
       // System.out.println("rows:"+i+" lines:"+j);
        for(int n=0;n<i;n++){
            if(dp[n][0]!=-1){
                dp[n][0] = 1;
            }
        }
        for(int m=0;m<j;m++){
            if(dp[0][m]!=-1){
                dp[0][m] = 1;
            }
        }
        for(int m=1;m<=i-1;m++){
            for(int n=1;n<=j-1;n++){
                if(dp[m][n]!=-1){
                    if(dp[m-1][n]==-1){
                        dp[m][n] = dp[m][n - 1];
                    }else if(dp[m][n-1]==-1){
                        dp[m][n] = dp[m - 1][n];
                    }else {
                        dp[m][n] = dp[m - 1][n] + dp[m][n - 1];
                    }
                }
            }
        }
        return dp[i-1][j-1];
    }

大家有想法和意见都可以交流,我之后还会定期更新牛客和LeetCode的算法题解法

  • 本文作者: dzou | 微信:17856530567
  • 本文链接: http://www.dzou.top/post/f08593ab.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!
  • 并保留本声明和上方二维码。感谢您的阅读和支持!