Lintcdoe 1479 能否到达终点
程序员文章站
2022-03-08 15:57:53
...
1479. 能否到达终点
中文English
给一个大小为 m*n
的map,1
代表空地,0
代表障碍物,9
代表终点。请问如果你从 (0, 0)
开始能否到达终点?
样例
样例1
输入:
[
[1,1,1],
[1,1,1],
[1,1,9]
]
输出: true
样例2
输入:
[
[1,1,1],
[1,0,0],
[1,0,9]
]
输出: false
//思路 :回溯法
public class Solution {
/**
* @param map: the map
* @return: can you reach the endpoint
*/
public boolean reachEndpoint(int[][] map) {
// Write your code here
int i= 0; int j =0;
int[][] arr = new int[map.length][map[0].length];
return Help(map,i,j,arr);
}
public static boolean Help(int[][] map , int i ,int j , int[][] arr){
if(i<0 || i>=map.length || j<0 || j>=map.length ) return false;
if(map[i][j] == 9) return true;
if(map[i][j] == 0 || arr[i][j] == 1) return false;
else {
arr[i][j]=1;
return (Help(map,i,j+1,arr) ||Help(map,i,j-1,arr)
||Help(map,i+1,j,arr) ||Help(map,i-1,j,arr) );
}
}
}