高度从小到大枚举每座山，然后比较该山对应编号两边的高度
public class AnimalPlacement {
private static final int N = 3; // 矩阵的大小
private static final int DOG = 1;
private static final int CAT = 2;
private static final int EMPTY = 0;
private int[][] grid = new int[N][N]; // 3x3的矩阵
private int x; // 狗的数量
private int y; // 猫的数量
private int count = 0; // 有效的放置方案数量

public AnimalPlacement(int x, int y) {  
    this.x = x;  
    this.y = y;  
}

public void placeAnimals() {  
    // 初始化矩阵为空  
    for (int i = 0; i < N; i++) {  
        for (int j = 0; j < N; j++) {  
            grid[i][j] = EMPTY;  
        }  
    }

    // 从(0, 0)开始放置动物  
    backtrack(0, 0);  
    System.out.println("Total valid placement schemes: " + count);  
}

private boolean backtrack(int row, int col) {  
    // 如果所有格子都填满了，返回true表示找到一种有效方案  
    if (row == N) {  
        return true;  
    }

    // 如果当前列填满了，则移到下一行  
    if (col == N) {  
        return backtrack(row + 1, 0);  
    }

    // 尝试在当前位置放置狗或猫  
    if (x > 0 && isSafe(row, col, DOG) && placeAnimal(row, col, DOG)) {  
        if (backtrack(row, col + 1)) {  
            return true;  
        }  
        removeAnimal(row, col); // 回溯  
    }

    if (y > 0 && isSafe(row, col, CAT) && placeAnimal(row, col, CAT)) {  
        if (backtrack(row, col + 1)) {  
            return true;  
        }  
        removeAnimal(row, col); // 回溯  
    }

    // 如果当前位置不能放置狗或猫，则尝试下一个位置  
    return backtrack(row, col + 1);  
}

private boolean isSafe(int row, int col, int animal) {  
    // 检查当前位置的上下左右是否已经有相同类型的动物  
    for (int i = -1; i <= 1; i++) {  
        for (int j = -1; j <= 1; j++) {  
            int newRow = row + i;  
            int newCol = col + j;  
            if (newRow >= 0 && newRow < N && newCol >= 0 && newCol < N && grid[newRow][newCol] == animal) {  
                return false;  
            }  
        }  
    }  
    return true;  
}

private boolean placeAnimal(int row, int col, int animal) {  
    if (grid[row][col] != EMPTY) {  
        return false;  
    }  
    grid[row][col] = animal;  
    if (animal == DOG) {  
        x--;  
    } else {  
        y--;  
    }  
    return true;  
}

private void removeAnimal(int row, int col) {  
    grid[row][col] = EMPTY;  
    if (grid[row][col] == DOG) {  
        x++;  
    } else {  
        y++;  
    }  
}

public static void main(String[] args) {  
    int dogs = 2; // 假设有2条狗  
    int cats = 1; // 假设有1只猫  
    AnimalPlacement placement = new AnimalPlacement(dogs, cats);  
    placement.placeAnimals();  
}

}