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

发表于 | 分类于 | |
字数统计: 455 字 | 阅读时长 ≈ 2 分钟
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;
}