我要招人

去企业版

首页 > 试题广场 >

机器人走方格I

[编程题]机器人走方格I

热度指数：13816 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定两个正整数int x,int y，代表一个x乘y的网格，现有一个机器人要从网格左上角顶点走到右下角，每次只能走一步且只能向右或向下走，返回机器人有多少种走法。保证x＋y小于等于12。

测试样例：

2,2

返回：2

算法知识视频讲解

推荐

莱昂纳多

由于题目中x+y<=12，所以不必担心递归超时问题，对于每一步，只要没有走到
边缘（x==1||y==1）就会有两种选择：向下走（x-1）or 向右走（y-1），终
止条件即走到边缘，只能一直走下去，即此时只有一种走法。

class Robot {
public:
    int countWays(int x, int y) {
        // write code here
        if(x<=0||y<=0) return 0;
        if(x==1||y==1) return 1;
        return countWays(x-1,y)+countWays(x,y-1);
    }
};

编辑于 2015-08-18 19:34:00 回复(21)

Java

猫哥💋

//最简洁的动态规划
import java.util.*;

public class Robot {
    public int countWays(int x, int y) {
        // write code here
        int[][] dp = new int[x][y];
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 1;
                }else {
                    dp[i][j] = dp[i-1][j]+dp[i][j-1];
                }
            }
        }
        return dp[x-1][y-1];
    }
}

编辑于 2020-04-01 09:01:52 回复(0)

Java

力喜

Java实现，已通过。递归求解。

如果选择向右转，走法数就是 countWays(x,y-1);
如果选择向下走，走法数就是 countWays(x-1,y)；
终止条件：当只有1行或1列时，走法数是1/

代码如下：

import java.util.*;
public class Robot {
    public int countWays(int x, int y) {
        // write code here
        if(x==1||y==1) return 1;
        return countWays(x-1,y)+countWays(x,y-1);
    }
}

发表于 2020-02-06 15:01:53 回复(0)

Java

我是大牛膜拜吧小白

import java.util.*;

public class Robot {
    public int countWays(int x, int y) {
        int[][] dp=new int[x][y];
        dp[0][0]=1;
        for(int i=1;i<x;i++){
            dp[i][0]=1;
        }
        for(int i=1;i<y;i++){
            dp[0][i]=1;
        }
        for(int i=1;i<x;i++){
            for(int j=1;j<y;j++){
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[x-1][y-1];
    }
}

发表于 2018-02-16 12:06:58 回复(0)

Java

面什么过什么

import java.util.*;

public class Robot {
    // 这个题有坑。。。x,y都是从1开始的，一开始想成从0开始了 - - 泪奔
    public int countWays(int x, int y) {
        if (x == 1 || y == 1) return 1;
        return countWays(x - 1, y) + countWays(x, y - 1);
    }
}

发表于 2017-07-19 10:48:21 回复(0)

Java

百乐门前一回首

//难点在于题目的理解
//方法一：递归
//方法二：滚动数组
import java.util.*;

public class Robot {
    public int countWays(int x, int y) {
        // write code here
        //return x*y+(int)Math.pow(2,(x-1)*(y-1));
        if(x==1 || y==1){
            return 1;
        }
        return countWays(x-1, y)+countWays(x, y-1);
    }
}

import java.util.*;

public class Robot {
    public int countWays(int x, int y) {
        // write code here
        int out[]=new int[y+1];//滚动数组，降二维为一维
        out[0]=0;
        for(int i=1;i<y+1;i++){
            out[i]=out[i]+1;
        }
       if(x==1||y==1)
            return out[Math.max(x,y)];
        for(int i=2;i<x+1;i++){
            for(int j=2;j<y+1;j++){
                out[j]=out[j-1]+out[j];
            }
        }
        return out[y];
    }
}

编辑于 2017-06-21 20:47:56 回复(0)

Java

Tinywz

很简单的一道题啊
public int countWays(int x, int y) {
	        // write code here
		 
	        return jiecheng(x+y)/(jiecheng(x)*jiecheng(y));
	    }
	 public int jiecheng(int n){
		 if(n==1)
			 return 1;
		 return n*jiecheng(n-1);
	 }

发表于 2017-05-05 12:23:30 回复(0)

Java

大闲人柴毛毛

机器人在X*Y的矩阵中走，每一步都有两种选择：要么向下、要么向右。

如果向下走，问题就变成：求(X-1)*Y矩阵中机器人的走法；

如果向右走，问题就变成：求X*(Y-1)矩阵中机器人的走法；

显然是递归的思想！

既然是递归，再考虑退出条件：当整个矩阵只有一行或一列的时候只有一种走法。

public class Robot {
    public int countWays(int x, int y) {
        if ( x==1 || y==1 ) 
            return 1;
        
        return countWays(x-1,y)+countWays(x,y-1);
    }
}

发表于 2017-04-02 15:15:00 回复(2)

Java

一神

/**
 * DFS的思路
 */
import java.util.*;

public class Robot {
    private int[][] direction = {
            {0, 0}, {0, 1}, {1, 0}
    };
    public int countWays(int x, int y) {
        // write code here
        boolean[][] book = new boolean[x][y];
        int[] res = new int[1];
        HashSet<String> set = new HashSet<String>();
        StringBuilder sBuilder = new StringBuilder();
        dfs(0, 0, x - 1, y - 1, book, res, set, sBuilder);
        return res[0];
    }

    public void dfs(int stx, int sty, int edx, int edy, boolean[][] book, int[] res, HashSet<String> set, StringBuilder sBuilder) {
        if (stx > edx || sty > edy) {
            return;
        }

        if (stx == edx && sty == edy) {
            if (!set.contains(sBuilder.toString()) && sBuilder.toString().split(";").length == (edx + edy + 1)) {
                res[0] ++;
                set.add(sBuilder.toString());
            }
        } else {
            for (int i = 0; i < 3; i ++) {
                int nextX = stx + direction[i][0];
                int nextY = sty + direction[i][1];

                if (nextX >= 0 && nextX <= edx && nextY >= 0 && nextY <= edy && !book[nextX][nextY]) {
                    book[nextX][nextY] = true;
                    String pair = nextX + "," + nextY + ";";
                    sBuilder.append(pair);
                    dfs(nextX, nextY, edx, edy, book, res, set, sBuilder);
                    int index = sBuilder.lastIndexOf(pair);
                    sBuilder = sBuilder.delete(index, sBuilder.length());
                    book[nextX][nextY] = false;
                }
            }
        }
    }
}

发表于 2017-03-13 10:44:17 回复(0)

Java

peng.tan

这个题目可以递归来解，如何递归呢？首先，我们需要一个递推公式，对于矩阵中的格子(i, j)，假设从(1, 1)到它的路径数量为path(i, j)，那么，有：

path(i, j) = path(i-1, j) + path(i, j-1)

很好理解，因为机器人只能向右或向下运动，因此它只能是从(i-1, j)或(i, j-1) 运动到(i, j)的，所以路径数量也就是到达这两个格子的路径数量之和。然后，我们需要一个初始条件，也就是递归终止条件，是什么呢？可以发现，当机器人在第一行时，不论它在第一行哪个位置，从(1, 1)到达那个位置都只有一条路径，那就是一路向右；同理，当机器人在第一列时，也只有一条路径到达它所在位置。

public class Robot {
    public int countWays(int x, int y) {
        if(x<=0||y<=0)
            return 0;
        else if(x==1||y==1)
            return 1;
        return countWays(x-1,y)+countWays(x,y-1);
    }
}

发表于 2016-10-07 11:33:37 回复(0)