PAT甲级——【牛客A1005】-白红宇

PAT甲级——【牛客A1005】

阅读量：4541 次

发布时间：2019-06-08

本文共 3369 字，大约阅读时间需要 11 分钟。

题目描述

Behind the scenes in the computer's memory, color is always talked about as a series of 24 bits of information for each pixel.  In an image, the color with the largest proportional area is called the dominant color.  A strictly dominant color takes more than half of the total area.  Now given an image of resolution M by N (for example, 800x600), you are supposed to point out the strictly dominant color.

输入描述:

Each input file contains one test case.  For each case, the first line contains 2 positive numbers: M (<=800) and N (<=600) which are the resolutions of the image.  Then N lines follow, each contains M digital colors in the range [0, 224).  It is guaranteed that the strictly dominant color exists for each input image.  All the numbers in a line are separated by a space.

输出描述:

For each test case, simply print the dominant color in a line.

输入例子:

5 30 0 255 16777215 2424 24 0 0 2424 0 24 24 24

输出例子:

版本一:

开始我以为主导颜色是指要连成一片的才算，零散分布不算，所以想了一个关于“岛问题”的解决方法，见版本二，后来才发现，原来就是数数，谁多，谁就是主导色

1 #include 
     
       2 #include 
      
        3 #include 
        4   5 using namespace std; 6   7 int main() 8 { 9     int M,N;10     int maxColor = 0;11     int resColor = 0;12     cin >> M >> N;13     map
        
         res;14     vector
         
          
           >data(M, vector
           
            (N, 0));15 for (int i = 0; i < N; ++i)16 {17 for (int j = 0; j < M; ++j)18 {19 int a;20 cin >> a;21 res[a]++; 22 }23 }24 for (auto ptr = res.begin(); ptr != res.end(); ++ptr)25 {26 if(ptr->second > maxColor)27 {28 maxColor = ptr->second;29 resColor = ptr->first;30 }31 }32 cout << resColor << endl;33 return 0;34 35 }

例版本一：

关于“岛问题”，使用递归遍历，就是对于每一种颜色，通过上下左右遍历出其所有的相同的颜色，并计数和标记，则得到每种颜色最多的主导色

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;int M, N;//方法一，使用void Travle(vector
         
          
           >&data, int a, int b, int &num, const int color){ if ( a < 0 || b < 0 || a >= M || b >= N|| data[a][b] != color) return; num++; data[a][b] = -1;//标记已遍历 Travle(data, a - 1, b, num, color); Travle(data, a + 1, b, num, color); Travle(data, a, b - 1, num, color); Travle(data, a, b + 1, num, color);}int main(){ Test1(); //M*N int maxColor = 0; int resColor = 0; cin >> M >> N; vector
           
            
             >data(M, vector
             
              (N, 0)); for (int i = 0; i < N; ++i) for (int j = 0; j < M; ++j) cin >> data[j][i]; for (int i = 0; i < M; ++i) { for (int j = 0; j < N; ++j) { if (data[i][j] >= 0)//未遍历过 { int num = 1; int color = data[i][j]; Travle(data, i, j, num, color); if (num > maxColor) { maxColor = num; resColor = color; } } } } cout << resColor << endl; return 0;}

版本三：

　　笨死了，英语理解能力不好，其实就是监测每次的输入，当输入某种颜色的个数过半，则立马输出!

1 #include 
     
       2 #include 
      
        3 #include 
       
         4   5 using namespace std; 6   7 int main() 8 { 9    int M, N;10     cin >> M >> N;11     unordered_map
        
         res;12     vector
         
          
           >data(M, vector
           
            (N, 0));13 for (int i = 0; i < N; ++i)14 {15 for (int j = 0; j < M; ++j)16 {17 int a;18 cin >> a;19 res[a]++;20 if (res[a] > M*N / 2)21 {22 cout << a << endl;23 break;24 }25 }26 } 27 return 0;28 29 }