¶ 题目0230-相同数字组成图形的周长
¶ 题目描述
有一个 的矩阵，每个元素的默认值为0，
现在向里面填充数字，相同的数字组成一个实心图形，
如下图所示是举行的局部(空白表示填充0)：
数字1组成了蓝色边框的实心图形，数字2组成了红色边框的实心图形。
单元格的边长规定为1个单位，
请根据输入，计算每个非0值填充出来的实心图形的周长。
¶ 输入描述
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
输入数据说明如下：
- 第一行输入 ，表示共有 个图形， 且 ;
- 矩阵左上角单元格坐标记作
(0,0),第一个数字表示行号，第二个数字表示列号; - 接下来是 行，每行第一个数字是矩阵单元格填充的数字，后续每两个一组，表示填充该数字的单元格坐标;
- 答题者无需考虑数据格式非法的场景，题目用例不考察数据格式;
- 题目用例保证同一个填充值只会有一行输入数据
¶ 输出描述
18 20
- 一共输出 个数值，每个数值表示某一行输入表示图形的周长;
- 输出顺序需和输入的各行顺序保持一致，即第1个数是输入的第1个图形的周长，第2个数是输入的第2个图形的周长，以此类推。
¶ 示例一
¶ 输入
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
¶ 输出
18 20
¶ 思路解析和复杂度分析
¶ 解题思路：
本题的目标是计算每个非0值填充出来的实心图形的周长。为了解决这个问题，我们可以遵循以下步骤：
- 初始化一个 64x64 的矩阵，将所有元素设置为0。
- 读取输入数据，包括填充数字的数量 N 和每个填充数字及其对应的坐标。
- 遍历每个填充数字，将矩阵中对应的单元格设置为填充值。
- 对于每个填充数字，计算其形成的实心图形的周长。
- 输出每个填充数字对应图形的周长。
在计算实心图形的周长时，我们需要检查矩阵中每个单元格的上、下、左、右四个邻居。如果邻居单元格的值与当前单元格的值不相等，或者邻居单元格不存在（位于矩阵边界外），则将当前单元格的边计入周长。
¶ 复杂度分析：
时间复杂度：整个算法的时间复杂度为 O(N * SIZE^2)，其中 N 是填充数字的数量，SIZE 是矩阵的尺寸。对于每个填充数字，我们需要遍历整个矩阵，因此时间复杂度与填充数字的数量和矩阵的大小成正比。
空间复杂度：空间复杂度为 O(SIZE^2)，因为我们需要存储一个 64x64 的矩阵。此外，我们还需要额外的空间来存储输入数据，但与矩阵相比，这部分空间消耗可以忽略不计。
总结：
本题的解决方案主要依赖于遍历整个矩阵以计算实心图形的周长。通过检查每个单元格的邻居，我们可以确定周长中的每一条边。由于矩阵的尺寸固定且较小（64x64），因此在实际运行中，算法的效率是可以接受的。
¶ 参考解题
¶ 参考解题 C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 64
int calculate_perimeter(int matrix[][SIZE], int N) {
int perimeter = 0;
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
if (matrix[i][j] == N) {
if (i == 0 || matrix[i - 1][j] != N) perimeter++;
if (j == 0 || matrix[i][j - 1] != N) perimeter++;
if (i == SIZE - 1 || matrix[i + 1][j] != N) perimeter++;
if (j == SIZE - 1 || matrix[i][j + 1] != N) perimeter++;
}
}
}
return perimeter;
}
int main() {
int N;
scanf("%d", &N);
getchar();
int matrix[SIZE][SIZE];
memset(matrix, 0, sizeof(matrix));
for (int i = 0; i < N; i++) {
int value;
scanf("%d", &value);
int x, y;
while (scanf("%d %d", &x, &y) == 2) {
matrix[x][y] = value;
}
getchar();
int perimeter = calculate_perimeter(matrix, value);
printf("%d", perimeter);
if (i != N - 1) {
printf(" ");
}
}
return 0;
}
¶ 参考解题 C++
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
using namespace std;
const int SIZE = 64;
int calculate_perimeter(const vector<vector<int>>& matrix, int N) {
int perimeter = 0;
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
if (matrix[i][j] == N) {
if (i == 0 || matrix[i - 1][j] != N) perimeter++;
if (j == 0 || matrix[i][j - 1] != N) perimeter++;
if (i == SIZE - 1 || matrix[i + 1][j] != N) perimeter++;
if (j == SIZE - 1 || matrix[i][j + 1] != N) perimeter++;
}
}
}
return perimeter;
}
int main() {
int N;
cin >> N;
cin.ignore();
vector<vector<int>> matrix(SIZE, vector<int>(SIZE, 0));
for (int i = 0; i < N; i++) {
string line;
getline(cin, line);
stringstream ss(line);
int value;
ss >> value;
int x, y;
while (ss >> x >> y) {
matrix[x][y] = value;
}
int perimeter = calculate_perimeter(matrix, value);
cout << perimeter;
if (i != N - 1) {
cout << " ";
}
}
return 0;
}
¶ 参考解题 Java
import java.util.Arrays;
import java.util.Scanner;
/**
* Created with IntelliJ IDEA.
* <br>Author: Amos
* <br>E-mail: amos@amoscloud.com
* <br>Date: 2023/3/22
* <br>Time: 10:35
* <br>Description: 100%
*/
public class Main0230 {
public static void main(String[] args) {
try (Scanner scanner = new Scanner(System.in)) {
int N = Integer.parseInt(scanner.nextLine());
int[][] matrix = new int[64][64];
for (int i = 0; i < N; i++) {
Integer[] split = Arrays.stream(scanner.nextLine().split(" "))
.map(Integer::parseInt)
.toArray(Integer[]::new);
int value = split[0];
for (int j = 1; j < split.length; j += 2) {
int row = split[j];
int col = split[j + 1];
matrix[row][col] = value;
}
}
scanner.close();
for (int i = 1; i <= N; i++) {
int perimeter = calculatePerimeter(matrix, i);
System.out.print(perimeter);
if (i != N) {
System.out.print(" ");
}
}
}
}
private static int calculatePerimeter(int[][] matrix, int value) {
int perimeter = 0;
for (int i = 0; i < 64; i++) {
for (int j = 0; j < 64; j++) {
if (matrix[i][j] == value) {
if (i == 0 || matrix[i - 1][j] != value) perimeter++;
if (i == 63 || matrix[i + 1][j] != value) perimeter++;
if (j == 0 || matrix[i][j - 1] != value) perimeter++;
if (j == 63 || matrix[i][j + 1] != value) perimeter++;
}
}
}
return perimeter;
}
}
¶ 参考解题 Python
def calculate_perimeter(matrix, N):
perimeter = 0
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if matrix[i][j] == N:
if i == 0 or matrix[i - 1][j] != N:
perimeter += 1
if j == 0 or matrix[i][j - 1] != N:
perimeter += 1
if i == len(matrix) - 1 or matrix[i + 1][j] != N:
perimeter += 1
if j == len(matrix[0]) - 1 or matrix[i][j + 1] != N:
perimeter += 1
return perimeter
if __name__ == "__main__":
N = int(input())
matrix = [[0] * 64 for _ in range(64)]
for _ in range(N):
data = list(map(int, input().split()))
value = data[0]
for i in range(1, len(data), 2):
x, y = data[i], data[i + 1]
matrix[x][y] = value
perimeter = calculate_perimeter(matrix, value)
print(perimeter, end=" ")
¶ 参考解题 JavaScript
const readline = require('readline');
const calculatePerimeter = (matrix, N) => {
let perimeter = 0;
for (let i = 0; i < matrix.length; i++) {
for (let j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] === N) {
if (i === 0 || matrix[i - 1][j] !== N) perimeter++;
if (j === 0 || matrix[i][j - 1] !== N) perimeter++;
if (i === matrix.length - 1 || matrix[i + 1][j] !== N) perimeter++;
if (j === matrix[0].length - 1 || matrix[i][j + 1] !== N) perimeter++;
}
}
}
return perimeter;
};
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
const matrix = new Array(64).fill(null).map(() => new Array(64).fill(0));
let N = 0;
let inputCount = 0;
rl.question('', (input) => {
N = parseInt(input);
rl.on('line', (line) => {
inputCount++;
const data = line.split(' ').map(Number);
const value = data[0];
for (let i = 1; i < data.length; i += 2) {
const x = data[i];
const y = data[i + 1];
matrix[x][y] = value;
}
const perimeter = calculatePerimeter(matrix, value);
process.stdout.write(perimeter.toString());
if (inputCount !== N) {
process.stdout.write(' ');
} else {
rl.close();
}
});
});