PAT-B 1068. 万绿丛中一点红(20)

传送门

https://www.patest.cn/contests/pat-b-practise/1068

题目

对于计算机而言,颜色不过是像素点对应的一个24位的数值。现给定一幅分辨率为MxN的画,要求你找出万绿丛中的一点红,即有独一无二颜色的那个像素点,并且该点的颜色与其周围8个相邻像素的颜色差充分大。
输入格式:
输入第一行给出三个正整数,分别是M和N(<= 1000),即图像的分辨率;以及TOL,是所求像素点与相邻点的颜色差阈值,色差超过TOL的点才被考虑。随后N行,每行给出M个像素的颜色值,范围在[0, 224)内。所有同行数字间用空格或TAB分开。
输出格式:
在一行中按照“(x, y): color”的格式输出所求像素点的位置以及颜色值,其中位置x和y分别是该像素在图像矩阵中的列、行编号(从1开始编号)。如果这样的点不唯一,则输出“Not Unique”;如果这样的点不存在,则输出“Not Exist”。
输入样例1:
8 6 200
由于这里不直观,直接放个表格上来:

0 0 0 0 0 0 0 0
65280 65280 65280 16711479 65280 65280 65280 65280
16711479 65280 65280 65280 16711680 65280 65280 65280
65280 65280 65280 65280 65280 65280 165280 165280
65280 65280 16777015 65280 65280 165280 65480 165280
16777215 16777215 16777215 16777215 16777215 16777215 16777215 16777215

输出样例1:
(5, 3): 16711680
输入样例2:
4 5 2
0 0 0 0
0 0 3 0
0 0 0 0
0 5 0 0
0 0 0 0
输出样例2:
Not Unique
输入样例3:
3 3 5
1 2 3
3 4 5
5 6 7
输出样例3:
Not Exist

分析

很烦的一题,改了好多次都没过,参考了各种代码,最后才知道坑在哪里,下面让我来简单说一下。

首先要写个判断“一点红”的函数,我那个方法写的很直观很好懂(其实是有点low,哈哈人艰不拆)。

接着要有一个判重的方法来判断数字是否重复,如果不重复并且满足“一点红”的条件才符合。

此条见题中原句:

对于计算机而言,颜色不过是像素点对应的一个24位的数值。现给定一幅分辨率为MxN的画,要求你找出万绿丛中的一点红,即有独一无二颜色的那个像素点,并且该点的颜色与其周围8个相邻像素的颜色差充分大。

觉得好坑是吗?是的,跟上我的脚步,后面还有更坑的。

代码写到目前为止,我天真的以为应该就可以A了,但是我万万没想到的是,问题出在了我的遍历方法。

刚才的题目中提到“周围8个相邻像素的颜色”,所以我很自然认为,最上、最左、最右、最下这四列,由于附近的像素构成不了8个,故舍去,但是这样的结果是两个检查点通过不了。

参考了网上各类代码后,发现成功的解法与我的解法的差别就在于对四个边元素的验证,只要对其进行验证,题目就能A掉,于是我给输入的数组四周补上了0,然后将四个边上的数也进行验证后,就通过了这道题,类似下图。

0 0 0 0 0
0 x x x 0
0 x x x 0
0 x x x 0
0 0 0 0 0

这就是我解题时遇到的各种问题,希望能解决大家的疑问。

源代码

//C/C++实现
#include <iostream>
#include <vector>
#include <cmath>
#include <map>

using namespace std;

bool isRed(int i, int j, vector<vector<int> > v, int tol){
    if (abs(v[i - 1][j - 1] - v[i][j]) <= tol){ // 左上角
        return false;
    }
    if (abs(v[i][j - 1] - v[i][j]) <= tol){ // 上
        return false;
    }
    if (abs(v[i + 1][j - 1] - v[i][j]) <= tol){ // 右上角
        return false;
    }
    if (abs(v[i + 1][j] - v[i][j]) <= tol){ // 右
        return false;
    }
    if (abs(v[i + 1][j + 1] - v[i][j]) <= tol){ // 右下角
        return false;
    }
    if (abs(v[i][j + 1] - v[i][j]) <= tol){ // 下
        return false;
    }
    if (abs(v[i - 1][j + 1] - v[i][j]) <= tol){ // 左下角
        return false;
    }
    if (abs(v[i - 1][j] - v[i][j]) <= tol){ // 左
        return false;
    }
    return true;
}

vector<vector<int> > v;

int main(){
    int m, n, tol;
    scanf("%d %d %d", &m, &n, &tol);
    // n行m列二维数组
    v.resize(n + 2);
    for (int i = 0; i < n + 2; ++i){
        v[i].resize(m + 2);
    }
    map<int, int> isRepeat;
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= m; ++j){
            scanf("%d", &v[i][j]);
            ++isRepeat[v[i][j]];
        }
    }
    int cnt = 0;
    int resI, resJ;
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= m; ++j){
            if (isRepeat[v[i][j]] == 1){ // 只出现过一次
                if (isRed(i, j, v, tol)){
                    ++cnt;
                    resI = i;
                    resJ = j;
                    if (cnt == 2){
                        break;
                    }
                }
            }
        }
        if (cnt == 2){
            break;
        }
    }
    if (cnt == 0){
        printf("Not Exist\n");
    }
    else if (cnt == 1){
        printf("(%d, %d): %d\n", resJ, resI, v[resI][resJ]);
    }
    else if (cnt == 2){
        printf("Not Unique\n");
    }
    return 0;
}

当前网速较慢或者你使用的浏览器不支持博客特定功能,请尝试刷新或换用Chrome、Firefox等现代浏览器