「PAT乙级真题解析」Basic Level 1068 万绿丛中一点红 (问题分析+完整步骤+伪代码描述+提交通过代码)
题设给定一幅画(/矩阵/二维数组), 要求检查每一个点和周围的点的差值是否都超过给定阈值. 同时要求统计每一个点值出现的次数, 给出只出现过一次并且跟周围点的差值都超过阈值的点。 如果这样的点不存在, 则输出"Not Exist"; 如果这样的点有多个, 则输出"Not Unique"; 否则, 按格式"(列号, 行号): 点值"输出该点信息
#算法#数据结构#c语言#pat考试#需求分析
Table of Contents
乙级的题目训练主要用来熟悉编程语言的语法和形成良好的编码习惯和编码规范。从小白开始逐步掌握用编程解决问题。
PAT乙级BasicLevelPractice 1068 万绿丛中一点红
问题分析
题设给定一幅画(/矩阵/二维数组), 要求检查每一个点和周围的点的差值是否都超过给定阈值. 同时要求统计每一个点值出现的次数, 给出只出现过一次并且跟周围点的差值都超过阈值的点。 如果这样的点不存在, 则输出"Not Exist"; 如果这样的点有多个, 则输出"Not Unique"; 否则, 按格式"(列号, 行号): 点值"输出该点信息
完整描述步骤
- 获取输入: 列数, 行数, 差值应大于的阈值
- 获取输入: 每一行每一列的像素点
- 统计各个点位置值出现的频次:
- 初始化统计器 = {0}
- 对于每一行每一列的点, 在统计器中将对应值的计数+1
- 初始化统计器:
- 满足题设条件的点的个数统计器 = 0;
- 对于每一行:
- 对于改行的每一列:
- 如果这个值只出现过一次:
- 对于周围8个相邻的位置:
- 如果这个位置没有超过图像范围:
- 检查该位置的与中心位置值的差值是否大于给定阈值
- 如果这个位置没有超过图像范围:
- 如果8个位置都满足条件:
- 题设条件的点的个数统计器计数+1
- 对于周围8个相邻的位置:
- 如果这个值只出现过一次:
- 对于改行的每一列:
- 检查满足题设条件的点个数:
- 如果为0, 则输出"Not Exist"
- 如果大于1, 则输出"Not Unique"
- 否则输出"(列号, 行号): 点值"
伪代码描述
- get input: col_amount, row_amount, difference_threshold
- get input: image (get iamge[row][col] for each row and each col)
- init recorder/counter:
- number_frequency = {0}
- for each row:
- for each col:
- number_frequency[iamge[row][col]]++;
- for each col:
- init counter/recorder:
- unique_x
- unique_y
- unique_pixel
- meet_condition_point_amount = 0
- directions = [ [0, 1], [0, -1], [1, 1], [1, 0], [1, -1], [-1, 1], [-1, 0], [-1, -1], ]
- for each row:
- for each col:
- if number_frequency[iamge[row][col]] == 1:
- init counter:
- meet_condition = 1;
- for each direction of directions:
- position_to_compare = (row + direction[0], col + direction[1]);
- if (0, 0) <= position_to_compare < (row_amount, col_amount):
- if abs(image[position_to_compare] - image[(row, col)]) <= difference_threshold:
- meet_condition = 0;
- break;
- if abs(image[position_to_compare] - image[(row, col)]) <= difference_threshold:
- if meet_condition == 1:
- unique_x = col + 1;
- unique_y = row + 1;
- unique_pixel = image[row][col];
- meet_condition_point_amount++;
- init counter:
- if number_frequency[iamge[row][col]] == 1:
- for each col:
- check meet_condition_point_amount:
- if meet_condition_point_amount == 0:
- print("Not Exist");
- else if meet_condition_point_amount > 1:
- print("No Unique");
- else:
- print("(unique_x, unique_y): unique_pixel");
- if meet_condition_point_amount == 0:
完整提交代码
/*
# 问题分析
题设给定一幅画(/矩阵/二维数组), 要求检查每一个点和周围的点的差值是否都超过给定阈值.
同时要求统计每一个点值出现的次数, 给出只出现过一次并且跟周围点的差值都超过阈值的点。
如果这样的点不存在, 则输出"Not Exist";
如果这样的点有多个, 则输出"Not Unique";
否则, 按格式"(列号, 行号): 点值"输出该点信息
# 完整描述步骤
1. 获取输入: 列数, 行数, 差值应大于的阈值
2. 获取输入: 每一行每一列的像素点
3. 统计各个点位置值出现的频次:
- 初始化统计器 = {0}
- 对于每一行每一列的点, 在统计器中将对应值的计数+1
4. 初始化统计器:
- 满足题设条件的点的个数统计器 = 0;
5. 对于每一行:
- 对于改行的每一列:
- 如果这个值只出现过一次:
- 对于周围8个相邻的位置:
- 如果这个位置没有超过图像范围:
- 检查该位置的与中心位置值的差值是否大于给定阈值
- 如果8个位置都满足条件:
- 题设条件的点的个数统计器计数+1
6. 检查满足题设条件的点个数:
- 如果为0, 则输出"Not Exist"
- 如果大于1, 则输出"Not Unique"
- 否则输出"(列号, 行号): 点值"
# 伪代码描述
1. get input: col_amount, row_amount, difference_threshold
2. get input: image (get iamge[row][col] for each row and each col)
2. init recorder/counter:
- number_frequency = {0}
3. for each row:
- for each col:
- number_frequency[iamge[row][col]]++;
4. init counter/recorder:
- unique_x
- unique_y
- unique_pixel
- meet_condition_point_amount = 0
- directions = [
[0, 1],
[0, -1],
[1, 1],
[1, 0],
[1, -1],
[-1, 1],
[-1, 0],
[-1, -1],
]
5. for each row:
- for each col:
- if number_frequency[iamge[row][col]] == 1:
- init counter:
- meet_condition = 1;
- for each direction of directions:
- position_to_compare = (row + direction[0], col + direction[1]);
- if (0, 0) <= position_to_compare < (row_amount, col_amount):
- if abs(image[position_to_compare] - image[(row, col)]) <= difference_threshold:
- meet_condition = 0;
- break;
- if meet_condition == 1:
- unique_x = col + 1;
- unique_y = row + 1;
- unique_pixel = image[row][col];
- meet_condition_point_amount++;
6. check meet_condition_point_amount:
- if meet_condition_point_amount == 0:
- print("Not Exist");
- else if meet_condition_point_amount > 1:
- print("No Unique");
- else:
- print("(unique_x, unique_y): unique_pixel");
*/
# include<stdio.h>
# include<math.h>
# define MAX_VALUE 16777220
int number_frequency[MAX_VALUE] = {0};
int image[1001][1001] = {0};
int directions[8][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0},
{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
int main(){
int col_amount, row_amount, difference_threshold;
scanf("%d %d %d", &col_amount, &row_amount, &difference_threshold);
for (int i = 0; i < row_amount; i++){
for (int j = 0; j < col_amount; j++){
scanf("%d", &image[i][j]);
number_frequency[image[i][j]]++;
}
}
int unique_x, unique_y, unique_pixel, meet_condition_point_amount = 0;
for ( int row_index = 0; row_index < row_amount; row_index++){
for (int col_index = 0; col_index < col_amount; col_index++){
if (number_frequency[image[row_index][col_index]] != 1){
continue;
}
int meet_condition = 1;
for (int k = 0; k < 8; k++){
int another_row_index = row_index + directions[k][0];
int another_col_index = col_index + directions[k][1];
if (another_row_index < 0 ||
another_row_index >= row_amount ||
another_col_index < 0 ||
another_col_index >= col_amount){
continue;
}
if (abs(image[row_index][col_index] - image[another_row_index][another_col_index]) <= difference_threshold){
meet_condition = 0;
break;
}
}
if (meet_condition == 1){
unique_x = col_index+1;
unique_y = row_index+1;
unique_pixel = image[row_index][col_index];
meet_condition_point_amount++;
}
}
}
if (meet_condition_point_amount == 1){
printf("(%d, %d): %d\n", unique_x, unique_y, unique_pixel);
} else if (meet_condition_point_amount == 0){
printf("Not Exist\n");
} else{
printf("Not Unique\n");
}
return 0;
}