华为笔试第三题,回溯法,不知哪里有问题。。
用回溯法,当前的点为(curX,curY),每次根据条件搜索上下左右,如果当前的点等于(z,w),那么全局count++。
But,每次都是45.45%,不知道哪里做错了,大家帮忙看看。
public class Main {
static int count = 0;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int m = scanner.nextInt();
int n = scanner.nextInt();
int[][] path = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
path[i][j] = scanner.nextInt();
}
}
int x = scanner.nextInt();
int y = scanner.nextInt();
int z = scanner.nextInt();
int w = scanner.nextInt();
back(path,x,y,z,w);
System.out.println(count%(int)(Math.pow(10,9)));
}
public static void back(int[][] path, int cuX, int cuY, int z, int w) {
if (cuX == z && cuY == w) {
count++;
return;
}
//上
if (cuX - 1 >= 0) {
int nextX = cuX - 1;
if (path[cuX][cuY] < path[nextX][cuY]) {
back(path, nextX, cuY, z, w);
}
}
//下
if (cuX + 1 < path.length) {
int nextX = cuX + 1;
if (path[cuX][cuY] < path[nextX][cuY]) {
back(path, nextX, cuY, z, w);
}
}
//左
if (cuY - 1 >= 0) {
int nextY = cuY - 1;
if (path[cuX][cuY] < path[cuX][nextY]) {
back(path, cuX, nextY, z, w);
}
}
//右
if (cuY + 1 < path[0].length) {
int nextY = cuY + 1;
if (path[cuX][cuY] < path[cuX][nextY]) {
back(path, cuX, nextY, z, w);
}
}
}
}
#华为##笔试题目#