首页 > 试题广场 >

货拉拉分布在全国各大城市的司机小哥，需要从公司出发，去到市内

[问答题]

货拉拉分布在全国各大城市的司机小哥，需要从公司出发，去到市内的业主待搬家的家里。已知他的位置以及业主的位置，但是由于城市道路交通的原因，他只能在左右中选定一个方向，在上下中选定一个方向，现在问他有多少种方案到达业主家。

给定一个地图map及它的长宽n和m，其中1代表设计师位置，2代表业主位置，-1代表不能经过的地区，0代表可以经过的地区，请返回方案数，保证一定存在合法路径。保证矩阵的长宽都小于等于10。

测试样例：

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

返回：2

添加回答
凯201903041803479头像 凯201903041803479
咋没人解析一波
发表于 2019-10-21 20:22:34 回复(1)
牛客658970523号头像 牛客658970523号 
 

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader;



public class Main{ public static void main(String[] args) throws IOException {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        String[] pram = br.readLine().split(" "); int n=Integer.parseInt(pram[0]); int m=Integer.parseInt(pram[1]);
        String[] sp = br.readLine().split(","); int [][] map=new int[n][m]; int row=0; int col=0; int si=0; int sj=0; for (int i = 0; i <sp.length ; i++) { if (i==m*(row)){
                col=0;
            }
            map[row][col]=Integer.parseInt(sp[i]); if (Integer.parseInt(sp[i])==1){
                si=row;
                sj=col;
            } if (i==m*(row+1)-1){
                row++;
            }
            col++;
        } int ans =process(si,sj,map);
        System.out.println(ans);
    } public static int process(int si ,int sj ,int [][] map){ int n=map.length; int m=map[0].length; if (si<0||si>=n||sj<0||sj>=m||map[si][sj]==-1){ return 0;
        } if (map[si][sj]==2){ return 1;
        }
        map[si][sj]=-1; int f1= process(si-1,sj,map); int f2=process(si+1,sj,map); int f3=process(si,sj-1,map); int f4=process(si,sj+1,map); return f1+f2+f3+f4;
    }
}

发表于 2022-02-06 12:51:54 回复(0)
cky19971头像 cky19971
dfs可以吗？记录经过的node和node对应的路径数。
发表于 2020-12-09 10:42:17 回复(0)
牛客279370402号头像 牛客279370402号 
    int[] row = new int[2];
    int[] col = new int[2];

    public int getWay(int[][] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                if (arr[i][j] == 1) {
                    row[0] = i;
                    col[0] = j;
                }
                if (arr[i][j] == 2) {
                    row[1] = i;
                    col[1] = j;
                }
            }
        }
        return dfs(arr, row[0], col[0]);
    }

    public int dfs(int[][] arr, int currentRow, int currentCol) {
        if (currentRow < 0 || currentRow >= arr.length || currentCol < 0 || currentCol >= arr[0].length || arr[currentRow][currentCol] == -1) {
            return 0;
        }
        if (arr[currentRow][currentCol] == 2) {
            return 1;
        }
        return (
                       row[1] > row[0] ?
                               dfs(arr, currentRow + 1, currentCol) :
                               dfs(arr, currentRow - 1, currentCol)) +
               (
                       col[1] > col[0] ?
                               dfs(arr, currentRow, currentCol + 1) :
                               dfs(arr, currentRow, currentCol - 1));
    }

发表于 2020-05-27 17:17:13 回复(0)
纯净·蓝头像 纯净·蓝
个人粗浅之见:
个人写的代码，没有优化，可以优化一下。如果有错误，请麻烦指正，如果有更好的解法，也可以提出来，互相学习。 

public static void main(String[] args) {
//        0,1,0],[2,0,0]
//        int[][] arr = new int[][]{
//                {0, 0, 0, 0, 0},
//                {0, 1, 0, 0, 0},
//                {0, 0, -1, 0, 0},
//                {0, 0, 0, 2, 0}
//        };
        int[][] arr = new int[][]{
                {0, 0, 0, 0, 0},
                {0, 0, 0, 1, 0},
                {0, 2, 0, 0, 0},
                {0, 0, 0, 0, 0}
        };
        System.out.println(dp(arr, arr.length, arr[0].length));
    }

    public static int dp(int[][] arr, int height, int width) {
        int x1 = 0, x2 = 0, y1 = 0, y2 = 0;
        int[] dp = new int[width];
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                if (arr[i][j] == 1) {
                    x1 = i; y1 = j;
                }
                if (arr[i][j] == 2) {
                    x2 = i; y2 = j;
                }
            }
        }

        dp[Math.min(y1, y2)] = 1;

        if ((x1 <= x2 && y1 <= y2) || (x1 > x2 && y1 > y2)) {

            for (int i = Math.min(x1, x2); i <= Math.max(x1, x2); i++) {
                for (int j = Math.min(y1, y2); j <= Math.max(y1, y2); j++) {
                    if (arr[i][j] == -1) dp[j] = 0;
                    else if (j > 0) dp[j] += dp[j - 1];
                }
            }
        } else {

            for (int i = Math.max(x1, x2); i >= Math.min(x1, x2); i--) {
                for (int j = Math.min(y1, y2); j <= Math.max(y1, y2); j++) {
                    if (arr[i][j] == -1) dp[j] = 0;
                    else if (j > 0) dp[j] += dp[j - 1];
                }
            }
        }
        Arrays.sort(dp);

        return dp[width - 1];
    }


发表于 2019-11-12 18:16:34 回复(0)
YCute头像 YCute 
public class Main{

   public static void main(String[] args) {

        int arr[][]={
            {0,1,0},
            {2,0,0}
        };

    System.out.println(BackNum(arr));

   }

   public static int BackNum(int arr[][]){

       String index1="";
       String index2 ="";

       for(int i=0;i<arr.length;i++){
           for(int j=0;j<arr[0].length;j++){
                if(arr[i][j]==1){
                    index1 = i+""+j;
                }
                if(arr[i][j]==2){
                    index2 = i+""+j;
                }
           }
       }

       int row = Math.abs(Integer.parseInt(index2)/10-Integer.parseInt(index1)/10)+1;
       int col = Math.abs(Integer.parseInt(index2)%10-Integer.parseInt(index1)%10)+1;

       if(row==col){
           return row*col-2-(row-2);
       }else{
           return row*col-2;
       }
   }
}

规律：
由题意可知，线路不可能从外面的大Map里面走（自己分析），只会从包含数据的小Map里面走才合乎规范，
例：0 1 0 0
       0 0 0 0
       0 0 0 2(总Map)
所有正确路线只会从
1 0 0
0 0 0
0 0 2（可行路线Map）
中产生，研究一下可行路线，发现规律，当可行数组为对称数组时，有row*col-2-(row-2)条可行路线（row和col代表可行路线Map的行和列）；
当可行路线Map不为对称数组时，则可能的线路为row*col-2； 
发表于 2019-11-07 20:55:04 回复(1)
jssd头像 jssd
没参考答案的么....
发表于 2019-11-07 11:08:34 回复(0)
提交观点

问题信息

安卓工程师 2018 货拉拉 Java工程师
来自：货拉拉2018秋招ja...
上传者：小小
难度：
7条回答 1917浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号