好几天没做题了,做两个题。最近因为头痛一直休息不好,买的砧石还带穴位图,我看过一段时间闲下来了得好好看看中医知识。

房间里面有一个机器人位于位置(0, 0)。房间的形状和面积都是未知的。你可以通过一个
遥控器来控制机器人往前后左右四个方向中的任何一个移动一个格子。
移动的函数是 boolean move(int direction), direction: 0, 1, 2, 3。如果机器人发现移动方向上被
墙壁挡住,这个方法会返回 false,否则这个函数就会返回 true,机器人就会移动到相应的位
置。

请实现一个函数,来找到房间的面积。
注:房间的形状是不规则的,但是是由许多大小为 1x1 的格子组成的,比如下图表示的房子
里面,每一个 X 表示一个格子,房间的总面积是 10

X
XXX X
XXXXX


解:首先想到的就是广度优先遍历吧,从00出发,走。不过代码一定要很熟练的写出来。

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static int result = 0;
    public static Queue<Integer> queue = new LinkedList<>();

    public static void main(String[] args) {
        char[][] arr = new char[][] { { 'x', ' ', ' ', ' ', ' ' }, { 'x', 'x', 'x', ' ', 'x' },
                { 'x', 'x', 'x', 'x', 'x' } };
        fun(arr, 0, 0, 'u');
        System.out.println(result);
    }

    public static void fun(char[][] arr, int x, int y, char used) {
        int m = arr.length;
        int n = arr[0].length;
        // 遍历上下左右
        if (x - 1 >= 0 && y >= 0 && arr[x - 1][y] == 'x') {
            queue.offer((x - 1) * 100 + y);
            arr[x - 1][y] = used;
            result++;
        }
        if (x + 1 < m && y >= 0 && arr[x + 1][y] == 'x') {
            queue.offer((x + 1) * 100 + y);
            arr[x + 1][y] = used;
            result++;
        }
        if (x >= 0 && y - 1 >= 0 && arr[x][y - 1] == 'x') {
            queue.offer(x * 100 + (y - 1));
            arr[x][y - 1] = used;
            result++;
        }
        if (x >= 0 && y + 1 < n && arr[x][y + 1] == 'x') {
            queue.offer(x * 100 + (y + 1));
            arr[x][y + 1] = used;
            result++;
        }
        while (!queue.isEmpty()) {
            Integer poll = queue.poll();
            fun(arr, poll / 100, poll % 100, used);
        }
    }
}


队列中的顺序是:

目前查找的是:1-0
目前查找的是:0-0
目前查找的是:2-0
目前查找的是:1-1
目前查找的是:2-1
目前查找的是:1-2
目前查找的是:2-2
目前查找的是:2-3
目前查找的是:2-4
目前查找的是:1-4
10


换另外一种思路,深度优先遍历也是可以的,主要是使用Stack

import java.util.Scanner;
import java.util.Stack;
public class Main4 {
    public static Stack<Integer> stack = null;
    public static int result = 0;
    //用来标记已经走过
    public static char used = 'u';
    public static void main(String[] args) {
        stack = new Stack<>();
        char[][] arr = {{'x',' ',' ', ' ',' '},{'x','x','x',' ','x'},{'x','x','x','x','x'}};
        fun(arr, 0, 0, 'x');
        System.out.println(result);
    }

    public static void fun(char[][] arr, int x, int y, char c) {
        int m = arr.length;
        int n =arr[0].length;
        // 遍历上下左右
        if (x - 1 >= 0 && y >= 0 && arr[x - 1][y] == 'x') {
            stack.push((x-1)*100+y);
            arr[x - 1][y] = used;
            result++;
        }
        if (x + 1 < m && y >= 0 && arr[x + 1][y] == 'x') {
            stack.push((x+1)*100+y);
            arr[x + 1][y] = used;
            result++;
        }
        if (x >= 0 && y - 1 >= 0 && arr[x][y - 1] == 'x') {
            stack.push(x*100+(y-1));
            arr[x][y - 1] = used;
            result++;
        }
        if (x >= 0 && y + 1 < n && arr[x][y + 1] == 'x') {    stack.push(x*100+(y+1));
            arr[x][y + 1] = used;
            result++;
        }
        while (!stack.isEmpty()) {
            int size = stack.size();
            int poll = stack.pop();
            System.out.println(poll);
            fun(arr, poll/100, poll%100, 'x');
        }
    }
}


会做也一定要在规定的时间内完成