货拉拉分布在全国各大城市的司机小哥,需要从公司出发,去到市内的业主待搬家的家里。已知他的位置以及业主的位置,但是由于城市道路交通的原因,他只能在左右中选定一个方向,在上下中选定一个方向,现在问他有多少种方案到达业主家。
给定一个地图map及它的长宽n和m,其中1代表设计师位置,2代表业主位置,-1代表不能经过的地区,0代表可以经过的地区,请返回方案数,保证一定存在合法路径。保证矩阵的长宽都小于等于10。
测试样例:
[[0,1,0],[2,0,0]],2,3
返回:2
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; } }
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)); }
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]; }
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; } } }