相同数字组成图形的周长(中等)

Posted on In Views:

1，问题描述

有一个64 6464x64 6464的矩阵，每个元素的默认值为0 00，现在向里面填充数字，相同的数字组成一个实心图形，如下图所示是矩阵的局部(空白表示填充0 00)

输入描述
第一行输入N NN，表示N NN个图形，N > 0 N > 0N>0且N < 64 N < 64N<64x64 6464
矩阵左上角单元格坐标记作(0 , 0 0,00,0)，第一个数字表示行号，第二个数字表示列号
接下来是N NN行，每行第一个数是矩阵单元格填充的数字，后续每两个一组，表示填充该数字的单元格坐标
答题者无需考虑数据格式非法的场景，题目用例不考察数据格式
题目用例保证同一个填充值只会有一行输入数据
输出描述
一共输出N NN个数值，每个数值表示某一行输入表示图形的周长
输出顺序需和输入的隔行顺序保持一致，即第1 11个数是输入的第1 11个图形的周长，第2 22个数是输入的第2 22个图形的周长，以此类推。

输入：

1
2
3
2
1 1 3 2 2 2 3 2 4 3 2 3 3 3 4 4 1 4 2 4 3 4 4 5 2 5 3
2 3 7 3 8 4 5 4 6 4 7 4 8 5 4 5 5 5 6 5 7 5 8 6 4 6 5 6 6 6 7 6 8 7 4 7 5 7 6 7 7 7 8

输出：

1
18 20

2，初步思考

​ 1，先构造grid二维图，以及一个

​ 2，缓存每个数字的一个位点即可

​ 3，每个数字的位点为起始点进行深度优先搜索

​ 创建一个visted 布尔类型二维图

​ 3.1，搜索到相关数字，就标记已被访问过

​ 3.2，搜索到虚拟边界，该数字的周长就自加一

​ 3.3，搜索到其他数字，该数字的周长就自加一

​ 4，循环3步骤，直到遍历完所有的数字

3，代码处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class code3 {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        boolean flag = true;
        int cnt = 0;
        int line = 0;
        int[][] grid = new int[64][64];
        boolean[][] visited = new boolean[64][64];
        List<int[]> list = new ArrayList<>();
        int[] res = new int[1];
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            if (flag) {
                line = Integer.parseInt(in.nextLine());
                res = new int[line];
                flag = false;
            } else {
                String a = in.nextLine();
                String[] split = a.split(" ");
                int n = (split.length - 1) / 2;
                int num = Integer.parseInt(split[0]);
                int[] ints = {cnt, num, Integer.parseInt(split[1]), Integer.parseInt(split[2])};
                list.add(ints);
                for (int i = 0; i < n; i++) {
                    int idx = i * 2 + 1;
                    int x = Integer.parseInt(split[idx]);
                    int y = Integer.parseInt(split[idx + 1]);
                    grid[x][y] = num;
                }
                cnt++;
                if (line == cnt) {
                    break;
                }
            }
        }


        System.out.println();
        // 处理数据，找到边界，沿着边界计算边长即可

        for (int[] ints : list) {
            dfs(grid, ints, ints[2], ints[3], visited, res);
        }

        // 输出
        StringBuilder sb = new StringBuilder();
        for (int re : res) {
            sb.append(re + " ");
        }
        String substring = sb.substring(0, sb.length() - 1);
        System.out.println(substring);
    }

    private static void dfs(int[][] grid, int[] ints, int x, int y, boolean[][] visited, int[] res) {
        if (x < 0 || x >= 64 || y < 0 || y >= 64) {
            res[ints[0]]++;// 边界也要加一
            return;
        }
        if (grid[x][y] != ints[1]) {
            res[ints[0]]++;
        } else if (!visited[x][y]) {// 暂未被访问到
            visited[x][y] = true;
            dfs(grid, ints, x - 1, y, visited, res);
            dfs(grid, ints, x, y - 1, visited, res);
            dfs(grid, ints, x + 1, y, visited, res);
            dfs(grid, ints, x, y + 1, visited, res);
        }
    }
}


/**
 * 2
 * 1 1 3 2 2 2 3 2 4 3 2 3 3 3 4 4 1 4 2 4 3 4 4 5 2 5 3
 * 2 3 7 3 8 4 5 4 6 4 7 4 8 5 4 5 5 5 6 5 7 5 8 6 4 6 5 6 6 6 7 6 8 7 4 7 5 7 6 7 7 7 8
 * 2
 * 1 ，1 3 ，2 2 ，2 3。 2 4， 3 2 3， 3 3 4， 4 1 4 ，2 4 3， 4 4 5， 2 5 3
 * 2 3 7 3 8 4 5 4 6 4 7 4 8 5 4 5 5 5 6 5 7 5 8 6 4 6 5 6 6 6 7 6 8 7 4 7 5 7 6 7 7 7 8
 */