java 二维数组中遇到障碍B无法穿越,K的值代表可以通行,写一段代码判断能否从指定的数T1找到目标数T2
时间: 2023-07-16 16:12:39 浏览: 36
假设二维数组为 `grid`,障碍物为字符 `'B'`,可以通行的字符为字符 `'K'`。目标数为 `T2`,起点为 `T1`。我们可以使用深度优先搜索(DFS)来判断能否到达目标数。
具体思路是:从起点开始进行DFS搜索,递归地向四个方向扩展,如果遇到障碍物或者越界,则返回上一层。如果找到了目标数,则返回 `true`,否则返回 `false`。代码如下:
```java
public static boolean canReachTarget(char[][] grid, int T1, int T2) {
int m = grid.length;
int n = grid[0].length;
boolean[][] visited = new boolean[m][n]; //记录是否访问过
int x = T1 / n; //T1在二维数组中的行号
int y = T1 % n; //T1在二维数组中的列号
return dfs(grid, visited, x, y, T2);
}
private static boolean dfs(char[][] grid, boolean[][] visited, int x, int y, int target) {
if (grid[x][y] == 'B' || visited[x][y]) { //如果遇到障碍物或者已经访问过了,返回false
return false;
}
visited[x][y] = true; //标记为已访问
if (grid[x][y] - '0' == target) { //如果找到了目标数,返回true
return true;
}
boolean up = x > 0 && dfs(grid, visited, x - 1, y, target); //向上搜索
boolean down = x < grid.length - 1 && dfs(grid, visited, x + 1, y, target); //向下搜索
boolean left = y > 0 && dfs(grid, visited, x, y - 1, target); //向左搜索
boolean right = y < grid[0].length - 1 && dfs(grid, visited, x, y + 1, target); //向右搜索
return up || down || left || right; //只要有一个方向能够到达目标数,就返回true
}
```
这段代码的时间复杂度为 $O(mn)$,其中 $m$ 和 $n$ 分别是二维数组的行数和列数。