我的PAT系列文章更新重心已移至Github绣夺，歡迎來看PAT題解的小伙伴請(qǐng)到Github Pages瀏覽最新內(nèi)容鹿驼。此處文章目前已更新至與Github Pages同步鸣剪。歡迎star我的repo零蓉。
題目
對(duì)于計(jì)算機(jī)而言卿嘲，顏色不過是像素點(diǎn)對(duì)應(yīng)的一個(gè) 24 位的數(shù)值】妒龋現(xiàn)給定一幅分辨率為
的畫宿百，要求你找出萬綠叢中的一點(diǎn)紅，即有獨(dú)一無二顏色的那個(gè)像素點(diǎn)洪添，并且該點(diǎn)的顏色與其周圍 8 個(gè)相鄰像素的顏色差充分大垦页。
輸入格式：
輸入第一行給出三個(gè)正整數(shù)，分別是 和
（
1000）干奢，即圖像的分辨率痊焊；以及 TOL，是所求像素點(diǎn)與相鄰點(diǎn)的顏色差閾值忿峻，色差超過
TOL 的點(diǎn)才被考慮薄啥。隨后 行，每行給出
個(gè)像素的顏色值逛尚，范圍在
內(nèi)垄惧。所有同行數(shù)字間用空格或 TAB 分開。
輸出格式：
在一行中按照 (x, y): color 的格式輸出所求像素點(diǎn)的位置以及顏色值绰寞，其中位置 x 和 y 分別是該像素在圖像矩陣中的列到逊、行編號(hào)（從
1 開始編號(hào)）铣口。如果這樣的點(diǎn)不唯一，則輸出 Not Unique觉壶；如果這樣的點(diǎn)不存在脑题，則輸出 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
思路
在這道題上我好像想多了铜靶，當(dāng)然也有可能陳越姥姥想少了（怎么可能叔遂，不可能的）。
首先就是争剿，“顏色差” 是什么已艰？網(wǎng)上其他人的做法99%（可能100%）都是直接把兩個(gè)顏色的值相減，結(jié)果的整數(shù)就是顏色差了蚕苇。
而我參考了Wiki: Color difference哩掺，
將(R, G, B)三維顏色空間的“距離”作為顏色差，這也是很合理的捆蜀。比如65280疮丛，也就是#00FF00，是綠色辆它，
而65279誊薄，#00FEFF，是青色锰茉，兩者在整數(shù)大小上相差1呢蔫，但是顏色有很大區(qū)別。幸好（或許也是不幸）在測(cè)試用例沒有使用上面這樣的例子飒筑，
我的測(cè)試結(jié)果和大家都是一樣的片吊。
然后就是大家都遇到的難(keng)點(diǎn)：
- 第一個(gè)難(keng)點(diǎn)：
要求你找出萬綠叢中的一點(diǎn)紅，即有獨(dú)一無二顏色的那個(gè)像素點(diǎn)
解讀：需要這個(gè)顏色在整幅圖中只出現(xiàn)一次协屡。
- 第二個(gè)難(keng)點(diǎn)：雖然題目說
該點(diǎn)的顏色與其周圍8個(gè)相鄰像素的顏色差充分大俏脊。
但是題目還是設(shè)置了處于邊界的滿足“條件”的點(diǎn)，所以說這又是一個(gè)題目敘述不清楚的案例（好多受害者）肤晓。
應(yīng)對(duì)這個(gè)問題目前看到的代碼中有兩個(gè)解決方案爷贫，一是加入邊界特殊情況的檢測(cè)，二是在題目數(shù)據(jù)的周圍加一圈0补憾。
第一個(gè)方案沒有問題漫萄。第二個(gè)方案我覺得是有問題的，如圖片的左上角有這樣的數(shù)據(jù)：
#000001 #0000FF ......
#0000FF #0000FF ......
...... ...... ......
假設(shè)顏色#000001在圖片只出現(xiàn)了這一次盈匾，這樣這個(gè)點(diǎn)應(yīng)該符合要求腾务。但是周圍加上0就變成了
#000000 #000000 #000000 ......
#000000 #000001 #0000FF ......
#000000 #0000FF #0000FF ......
...... ...... ...... ......
不管顏色差是怎么算的，這個(gè)中間的#000001都是不能被檢測(cè)出來的削饵。但是又很幸運(yùn)地岩瘦，我看使用這個(gè)方法的代碼也都通過了未巫。
我能說什么呢 :)
P.S.
關(guān)于代碼優(yōu)化：這個(gè)代碼運(yùn)行時(shí)間好長（160+ms），應(yīng)該是判斷顏色唯一太耗時(shí)了担钮，相當(dāng)于O(N2*M2)橱赠，
或許改為用另一個(gè)排序好的列表查找會(huì)好很多（預(yù)計(jì)時(shí)間復(fù)雜度為M*N*log(M*N)）尤仍。
更新：上面的判斷竟然是錯(cuò)的箫津，我在本地測(cè)試了上述方案，使用最多的數(shù)據(jù)1000*1000宰啦，排序加查找竟然比原來的方案耗時(shí)多一個(gè)數(shù)量級(jí)
～～～o(>﹏<)o苏遥。之前的方案從文件讀取用了0.2秒，但是查找只用了0.04秒（其中iUnique函數(shù)只有0.02秒Ｉ哪！）田炭。
新的方案qsort用了0.2秒，查找（使用了bsearch）用了0.3秒漓柑！這不科學(xué) (ㄒoㄒ) （難道是被stdlib坑了教硫？）
（證明瓶頸在數(shù)據(jù)讀取上，那運(yùn)行時(shí)間長的鍋我就不背了）
代碼
最新代碼@github辆布，歡迎交流
#include <stdio.h>
#define SQR(X) ((X)*(X))
#define R(COLOR) ((COLOR & 0XFF0000) >> 16)
#define G(COLOR) ((COLOR & 0X00FF00) >> 8)
#define B(COLOR) (COLOR & 0X0000FF)
#define D(C1, C2) (SQR(R(C1) - R(C2)) + SQR(G(C1) - G(C2)) + SQR(B(C1) - B(C2)))
int iUnique(int array[][1000], int x, int y, int x0, int y0)
{
for(int i = 0; i < x; i++)
for(int j = 0; j < y; j++)
if(array[i][j] == array[x0][y0] && !(i == x0 && j == y0))
return 0;
return 1;
}
int main()
{
int M, N, TOL;
scanf("%d %d %d", &M, &N, &TOL);
int fig[1000][1000];
for(int i = 0; i < N; i++)
for(int j = 0; j < M; j++)
scanf("%d", &fig[i][j]);
int count = 0, M0, N0;
for(int i = 0; i < N; i ++)
for (int j = 0; j < M; j++)
if((i > 0 && j > 0 ? D(fig[i][j], fig[i - 1][j - 1]) > SQR(TOL) : 1)
&& (i > 0 ? D(fig[i][j], fig[i - 1][j ]) > SQR(TOL) : 1)
&& (i > 0 && j < M ? D(fig[i][j], fig[i - 1][j + 1]) > SQR(TOL) : 1)
&& ( j > 0 ? D(fig[i][j], fig[i ][j - 1]) > SQR(TOL) : 1)
&& ( j < M ? D(fig[i][j], fig[i ][j + 1]) > SQR(TOL) : 1)
&& (i < N && j > 0 ? D(fig[i][j], fig[i + 1][j - 1]) > SQR(TOL) : 1)
&& (i < N ? D(fig[i][j], fig[i + 1][j ]) > SQR(TOL) : 1)
&& (i < N && j < M ? D(fig[i][j], fig[i + 1][j + 1]) > SQR(TOL) : 1)
&& iUnique(fig, N, M, i, j))
{
count++;
N0 = i;
M0 = j;
}
if(count == 0) printf("Not Exist");
if(count == 1) printf("(%d, %d): %d", M0 + 1, N0 + 1, fig[N0][M0]);
if(count >= 2) printf("Not Unique");
return 0;
}
