PAT B1068 万绿丛中一点红(C++)

PAT甲级目录 | PAT乙级目录

题目描述

B1068 万绿丛中一点红

解题思路

逻辑查找。用 map 记录每种颜色出现的次数,用于后面判断某种颜色是否唯一。用方向数组来确定方向,只要对数组进行遍历就能获得全部方向。因为只要求在结果唯一时输出该点,因此只需要记录一个坐标以及可能的点数 cnt 就足够了,只有 cnt = 1 时才输出坐标。

易错点

  • 寻找的是颜色唯一的点
  • 行和列不要弄反,可以前面都按照习惯用(行,列),最后倒过来输出

也许陌生的知识点

  • map<int, int> color;
    • 用于映射,键和值可以是任意类型
    • 直接使用 m[<键>] = <值> 即可向map中添加一组键值对
    • 需要的头文件:map

代码示例:

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
#include <cstdio>
#include <cmath>
#include <map>
using namespace std;
int m, n, tol, pic[1005][1005];
map<int, int> color;
bool check(int i, int j){ // 与周围一圈的点比较
int cnt = 0, dx[] = {-1, -1, -1, 0, 1, 1, 1, 0}, dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};
for(int k = 0; k < 8; k++){
if(abs(pic[i][j] - pic[i + dx[k]][j + dy[k]]) > tol) cnt++;
}
return cnt == 8;
}
int main(){
int ans[2], cnt = 0;
scanf("%d %d %d", &m, &n, &tol);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
scanf("%d", &pic[i][j]);
color[pic[i][j]]++;
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(check(i, j) && color[pic[i][j]] == 1){ // 颜色唯一的点
ans[0] = i;
ans[1] = j;
cnt++; // 符合条件的计数
}
}
}
if(cnt == 0) printf("Not Exist\n");
else if(cnt > 1) printf("Not Unique\n");
else printf("(%d, %d): %d\n", ans[1], ans[0], pic[ans[0]][ans[1]]);
return 0;
}