如何用深度优先搜索（DFS）查找二维数组的相邻位置

需求：使用深度优先搜索（DFS）查找二维数组中值为1的相邻位置。
示例二维数组：

{{0,0,0,0,0},
 {0,1,1,1,0},
 {0,1,1,1,0},
 {0,1,1,1,0},
 {0,0,0,1,1}}

调用dfs(2,2)（此处为1-based索引，对应数组第二行第二列的1）时，需输出所有值为1的相邻位置：(1,1),(1,2),(1,3),(2,1),(2,3),(3,1),(3,2),(3,3)

以下是用户尝试编写的Java代码：

public class Main {
    public static void main(String[] args) {
        dfs(1,1);
    }

    static int N = 5;
    static int M = 5;

    static boolean[][] vis = new boolean[1001][1001];
    static int[][] arr ={{0,0,0,0,0},
                        {0,1,0,1,0},
                        {0,1,1,1,0},
                        {0,1,0,0,0},
                        {0,0,0,0,0}};

    public static boolean isValid(int x,int y){
        if(x<=0 || x>N || y<=0 || y>M){
            return false;
        }
        if(vis[x][y] == true){
            return false;
        }
        return true;
    }

    static void dfs(int x,int y){
        int[] dx = {-1,0,1,0};
        int[] dy = {0,1,0,-1};

        vis[x][y] = true;
        System.out.println("row: "+x+" col: "+y);

        for(int i =0;i<4;i++){
            if(isValid(x+dx[i],y+dy[i])){
                dfs(x+dx[i],y+dy[i]);
            }
        }
    }
}

代码问题及修正方案 #

问题点： #

1. 索引逻辑混乱：Java数组是0-based索引，但代码用1-based做边界判断，和需求的索引规则不统一；
2. 未过滤值为0的位置：代码没检查数组值是否为1，会遍历无效的0元素；
3. 输出格式不符：当前输出是row: x col: y，不符合需求的(x,y)格式；
4. 内存浪费：vis数组定义为1001x1001，远大于实际数组尺寸；
5. 初始调用错误：需求调用dfs(2,2)，但代码里调用的是dfs(1,1)。

修正后的代码： #

import java.util.ArrayList;
import java.util.List;

public class Main {
    // 示例目标数组
    static int[][] arr = {
            {0, 0, 0, 0, 0},
            {0, 1, 1, 1, 0},
            {0, 1, 1, 1, 0},
            {0, 1, 1, 1, 0},
            {0, 0, 0, 1, 1}
    };
    static boolean[][] vis;
    static List<String> result = new ArrayList<>();

    public static void main(String[] args) {
        int rows = arr.length;
        int cols = arr[0].length;
        vis = new boolean[rows][cols];
        // 需求的(2,2)是1-based，转换为0-based索引(1,1)
        dfs(1, 1);
        // 按要求格式输出结果
        System.out.println(String.join(",", result));
    }

    // 校验坐标合法、值为1且未被访问
    public static boolean isValid(int x, int y) {
        int rows = arr.length;
        int cols = arr[0].length;
        if (x < 0 || x >= rows || y < 0 || y >= cols) {
            return false;
        }
        return arr[x][y] == 1 && !vis[x][y];
    }

    static void dfs(int x, int y) {
        vis[x][y] = true;
        // 上下左右四个方向
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (isValid(nx, ny)) {
                // 转换为1-based格式存入结果
                result.add(String.format("(%d,%d)", nx + 1, ny + 1));
                dfs(nx, ny);
            }
        }
    }
}

修正说明： #

• 统一用0-based处理数组，输出时转换为需求的1-based格式；
• isValid增加值为1的判断，确保只遍历有效元素；
• 用List收集结果，最后按要求格式拼接输出；
• vis数组大小与原数组一致，避免内存浪费；
• 初始调用转换为对应0-based索引，匹配需求的调用参数。

内容的提问来源于stack exchange，提问作者Senura Asanka