华为OD真题：学习成长记录篇：深度优先搜索算法+递归思想

- 日理万妓 2023-09-24 13:50 8阅读 0赞

题目描述：

小华和小为相约一起去吃饭，他们需要选取餐厅，要求双方都能到达，请你计算他们可能会去的餐厅。在一个m\*n的地图上，数字0代表道路，数字1代表障碍物，数字2代表小华或小为的起始位置（非障碍物），有且仅有2个点。数字3代表餐厅（非障碍物）。

**输入描述：** 第一行输入m和n（空格分隔），代表地图的行和列。接下来m行、每行n个数字（0-3）表示对应位置的类型（以空格分隔）

**输出描述：** 小华和小为都能到达的餐厅数量

测试用例：

4 4

2 1 2 3
    
    1 0 1 0
    
    1 1 0 0
    
    0 1 0 0

输出：0

..................

4 4

`2 1 0 3`

`0 1 2 1`

`0 3 0 0`

`0 0 0 0`

输出：2

记录原因：在网上没搜到相关的此题的java代码的解题思路跟步骤，故在此做记录，希望能提供点帮助，下面代码非最优解（比较适合算法入门者理解），还需要完善，相关数据请用变量替代，简化了部分代码。如：数组的深度复制，数据的输入处理等

解题思路：

1.记录当前的小华、小为坐标

2.分别递归下四个方向前进，前进时能走通（不为0）时，取一个特殊值表示已经走过的路，防止重复计算。

3.走不通时，则返回上一步，继续选择一个方向去前进

4. 2-3的步骤过程优先考虑DFS（深度优先搜索算法）、递归算法思想实现

5.计算结果，找到餐厅的值坐标（value =3），此坐标下小华小为的值为99，则表示这俩人都走过此路，则成功计算+1；

代码如下：

public class FindRestaurant {
    public static void main(String[] args) {
    //输入的测试数据
    int[][] tab = {
            {2, 1, 0, 3},
            {0, 1, 2, 1},
            {0, 3, 0, 0},
            {0, 0, 0, 0}
    };

int\[\]\[\] tab1 = \{ \{2, 1, 0, 3\}, \{0, 1, 2, 1\}, \{0, 3, 0, 0\}, \{0, 0, 0, 0\} \};

int\[\]\[\] tab2 = \{ \{2, 1, 0, 3\}, \{0, 1, 2, 1\}, \{0, 3, 0, 0\}, \{0, 0, 0, 0\} \};

//复制一份（未采用数组的深度复制）
            int[][] huaTab = tab1;
            int[][] weiTab = tab2;
            //移动的四个方位
            int dx[] = {1, 0, -1, 0};
            int dy[] = {0, -1, 0, 1};
            //找出2人的当前位置
            int[] hua = {0, 0};
            int[] wei = {0, 2};
            //小华能走到的路
            find(hua ,dx,dy,huaTab,tab1);
    
            //小为能走到的路
            find(wei,dx,dy,weiTab,tab2);
    
            //当值为2，且小华小为都走过此路=99
            int suc = 0;
            for (int j = 0; j < tab.length;j++) {
                for (int i = 0; i < tab.length;i++){
                    if (tab[j][i] == 2 &&  weiTab[i][j] == 99 && huaTab [i][j] == 99){
                        suc ++;
                    }
                }
            }
            System.out.println(suc);//输出值
        }
        //递归重复往四个方向走去
        public static void find(int [] people ,int dx[],int dy[],int peopleTab[][],int tab[][] ){
            for (int i = 0; i < 4; i++) {
                int x = people[0] + dx[i];
                int y = people[1] + dy[i];
                //表示当前路在界限内可以走
                if (x >= 0 && x < 4 && y >= 0 && y < 4) {
                    int value = tab[x][y];
                    if (value != 0 && value != 99){
                        //赋值一个特殊值防止走重复的路，防止死循环，将走过的路都刷成99
                        peopleTab[x][y] = 99;
                        int []temp = {x,y};
                        //重复往下执行一路走下去
                        find(temp,dx,dy,peopleTab,tab);
                    }
                }
            }
        }
    }