Étant donné une matrice de N lignes et M Les colonnes se composent de trois valeurs {r g b}. La tâche consiste à trouver l'aire du plus grand triangle dont un côté est parallèle à l'axe y, c'est-à-dire vertical et la couleur des trois sommets est différente.
Exemples :  
 

    Input :      N = 4 M =5   
  mat[][] =   
  {   
  r r r r r   
  r r r r g   
  r r r r r   
  b b b b b   
  }   
    Output :     10   
 The maximum area of triangle is 10.   
 Triangle coordinates are (00) containing r (14) containing g (30) containing b.  
   
  
    
 Nous connaissons l'aire d'un triangle = 1/2 * base * hauteur, nous devons donc maximiser la base et la hauteur du triangle. Puisqu’un côté est parallèle à l’axe des y, nous pouvons considérer ce côté comme la base du triangle.   
 Pour maximiser la base, nous pouvons trouver la première et la dernière occurrence de {r g b} pour chaque colonne. Nous avons donc deux ensembles de 3 valeurs pour chaque colonne. Pour la base de n'importe quelle colonne, un sommet appartient au premier ensemble et le deuxième sommet au deuxième ensemble, de sorte qu'ils ont des valeurs différentes.   
 Pour maximiser la hauteur de n'importe quelle colonne comme base, le troisième sommet doit être choisi de telle sorte que le sommet soit le plus éloigné de la colonne sur le côté gauche ou droit de la colonne ayant une valeur différente des deux autres sommets.    
 Maintenant, pour chaque colonne, trouvez l’aire maximale du triangle.   
 Ci-dessous la mise en œuvre de cette approche :   
    
 C++   
   // C++ program to find maximum area of triangle   // having different vertex color in a matrix.   #include       using     namespace     std  ;   #define R 4   #define C 5   // return the color value so that their corresponding   // index can be access.   int     mapcolor  (  char     c  )   {      if     (  c     ==     'r'  )      return     0  ;      else     if     (  c     ==     'g'  )      return     1  ;      else     if     (  c     ==     'b'  )      return     2  ;   }   // Returns the maximum area of triangle from all   // the possible triangles   double     findarea  (  char     mat  [  R  ][  C  ]     int     r       int     c        int     top  [  3  ][  C  ]     int     bottom  [  3  ][  C  ]      int     left  [  3  ]     int     right  [  3  ])   {      double     ans     =     (  double  )  1  ;      // for each column      for     (  int     i     =     0  ;     i      <     c  ;     i  ++  )      // for each top vertex      for     (  int     x     =     0  ;     x      <     3  ;     x  ++  )      // for each bottom vertex      for     (  int     y     =     0  ;     y      <     3  ;     y  ++  )      {      // finding the third color of      // vertex either on right or left.      int     z     =     3     -     x     -     y  ;      // finding area of triangle on left side of column.      if     (  x     !=     y     &&     top  [  x  ][  i  ]     !=     INT_MAX     &&      bottom  [  y  ][  i  ]     !=     INT_MIN     &&     left  [  z  ]     !=     INT_MAX  )      {      ans     =     max  (  ans       ((  double  )  1  /  (  double  )  2  )     *      (  bottom  [  y  ][  i  ]     -     top  [  x  ][  i  ])     *      (  i     -     left  [  z  ]));      }      // finding area of triangle on right side of column.      if     (  x     !=     y     &&     top  [  x  ][  i  ]     !=     INT_MAX     &&      bottom  [  y  ][  i  ]     !=     INT_MIN     &&      right  [  z  ]     !=     INT_MIN  )      {      ans     =     max  (  ans       ((  double  )  1  /  (  double  )  2  )     *      (  bottom  [  y  ][  i  ]     -     top  [  x  ][  i  ])     *      (  right  [  z  ]     -     i  ));      }      }      return     ans  ;   }   // Precompute the vertices of top bottom left   // and right and then computing the maximum area.   double     maxarea  (  char     mat  [  R  ][  C  ]     int     r       int     c  )   {      int     left  [  3  ]     right  [  3  ];      int     top  [  3  ][  C  ]     bottom  [  3  ][  C  ];      memset  (  left       INT_MAX       sizeof     left  );      memset  (  right       INT_MIN       sizeof     right  );      memset  (  top       INT_MAX       sizeof     top  );      memset  (  bottom       INT_MIN       sizeof     bottom  );      // finding the r b g cells for the left      // and right vertices.      for     (  int     i     =     0  ;     i      <     r  ;     i  ++  )      {      for     (  int     j     =     0  ;     j      <     c  ;     j  ++  )      {      left  [  mapcolor  (  mat  [  i  ][  j  ])]     =      min  (  left  [  mapcolor  (  mat  [  i  ][  j  ])]     j  );      right  [  mapcolor  (  mat  [  i  ][  j  ])]     =      max  (  left  [  mapcolor  (  mat  [  i  ][  j  ])]     j  );      }      }      // finding set of {r g b} of top and      // bottom for each column.      for     (  int     j     =     0  ;     j      <     c  ;     j  ++  )      {      for  (     int     i     =     0  ;     i      <     r  ;     i  ++  )      {      top  [  mapcolor  (  mat  [  i  ][  j  ])][  j  ]     =      min  (  top  [  mapcolor  (  mat  [  i  ][  j  ])][  j  ]     i  );      bottom  [  mapcolor  (  mat  [  i  ][  j  ])][  j  ]     =      max  (  bottom  [  mapcolor  (  mat  [  i  ][  j  ])][  j  ]     i  );      }      }      return     findarea  (  mat       R       C       top       bottom       left       right  );   }   // Driven Program   int     main  ()   {      char     mat  [  R  ][  C  ]     =      {      'r'       'r'       'r'       'r'       'r'        'r'       'r'       'r'       'r'       'g'        'r'       'r'       'r'       'r'       'r'        'b'       'b'       'b'       'b'       'b'        };      cout      < <     maxarea  (  mat       R       C  )      < <     endl  ;      return     0  ;   }   
  Java   
   import     java.util.Arrays  ;   public     class   Main     {      static     int     R     =     4  ;      static     int     C     =     5  ;      static     char  [][]     mat     =     {      {  'r'       'r'       'r'       'r'       'r'  }      {  'r'       'r'       'r'       'r'       'g'  }      {  'r'       'r'       'r'       'r'       'r'  }      {  'b'       'b'       'b'       'b'       'b'  }      };      public     static     void     main  (  String  []     args  )     {      System  .  out  .  println  (  maxArea  (  mat       R       C  ));      }      // Returns the color value so that their corresponding index can be accessed.      static     int     mapColor  (  char     c  )     {      if     (  c     ==     'r'  )     return     0  ;      else     if     (  c     ==     'g'  )     return     1  ;      else     if     (  c     ==     'b'  )     return     2  ;      else     return     -  1  ;      }      // Returns the maximum area of triangle from all the possible triangles      static     double     findArea  (  char  [][]     mat       int     r       int     c       int  [][]     top       int  [][]     bottom       int  []     left       int  []     right  )     {      double     ans     =     10  ;      // For each column      for     (  int     i     =     0  ;     i      <     c  ;     i  ++  )     {      // For each top vertex      for     (  int     x     =     0  ;     x      <     3  ;     x  ++  )     {      // For each bottom vertex      for     (  int     y     =     0  ;     y      <     3  ;     y  ++  )     {      // Finding the third color of vertex either on right or left.      int     z     =     3     -     x     -     y  ;      // Finding area of triangle on left side of column.      if     (  x     !=     y     &&     top  [  x  ][  i  ]     !=     Integer  .  MAX_VALUE     &&      bottom  [  y  ][  i  ]     !=     Integer  .  MIN_VALUE     &&      left  [  z  ]     !=     Integer  .  MAX_VALUE  )     {      ans     =     Math  .  max  (  ans       0.5     *      (  bottom  [  y  ][  i  ]     -     top  [  x  ][  i  ]  )     *     (  i     -     left  [  z  ]  ));      }      // Finding area of triangle on right side of column.      if     (  x     !=     y     &&     top  [  x  ][  i  ]     !=     Integer  .  MAX_VALUE     &&      bottom  [  y  ][  i  ]     !=     Integer  .  MIN_VALUE     &&      right  [  z  ]     !=     Integer  .  MIN_VALUE  )     {      ans     =     Math  .  max  (  ans       0.5     *      (  bottom  [  y  ][  i  ]     -     top  [  x  ][  i  ]  )     *     (  right  [  z  ]     -     i  ));      }      }      }      }      return     ans  ;      }      // Precompute the vertices of top bottom left and right and then computing the maximum area.      static     double     maxArea  (  char  [][]     mat       int     r       int     c  )     {      int  []     left     =     new     int  [  3  ]  ;      Arrays  .  fill  (  left       Integer  .  MAX_VALUE  );      int  []     right     =     new     int  [  3  ]  ;      Arrays  .  fill  (  right       Integer  .  MIN_VALUE  );      int  [][]     top     =     new     int  [  3  ][  c  ]  ;      for     (  int  []     row     :     top  )     Arrays  .  fill  (  row       Integer  .  MAX_VALUE  );      int  [][]     bottom     =     new     int  [  3  ][  c  ]  ;      for     (  int  []     row     :     bottom  )     Arrays  .  fill  (  row       Integer  .  MIN_VALUE  );      // Finding the r b g cells for the left and right vertices.      for     (  int     i     =     0  ;     i      <     r  ;     i  ++  )     {      for     (  int     j     =     0  ;     j      <     c  ;     j  ++  )     {      int     color     =     mapColor  (  mat  [  i  ][  j  ]  );      left  [  color  ]     =     Math  .  min  (  left  [  color  ]       j  );      right  [  color  ]     =     Math  .  max  (  right  [  color  ]       j  );      }      }      // Finding set of {r g b} of top and bottom for each column.      for     (  int     j     =     0  ;     j      <     c  ;     j  ++  )     {      for     (  int     i     =     0  ;     i      <     r  ;     i  ++  )     {      int     color     =     mapColor  (  mat  [  i  ][  j  ]  );      top  [  color  ][  j  ]     =     Math  .  min  (  top  [  color  ][  j  ]       i  );      bottom  [  color  ][  j  ]     =     Math  .  max  (  bottom  [  color  ][  j  ]       i  );      }      }      return     findArea  (  mat       r       c       top       bottom       left       right  );      }   }   
  Python3   
   # Python3 program to find the maximum    # area of triangle having different    # vertex color in a matrix.    # Return the color value so that their    # corresponding index can be access.    def   mapcolor  (  c  ):   if   c   ==   'r'  :   return   0   elif   c   ==   'g'  :   return   1   elif   c   ==   'b'  :   return   2   # Returns the maximum area of triangle    # from all the possible triangles    def   findarea  (  mat     r     c     top     bottom     left     right  ):   ans   =   1   # for each column    for   i   in   range  (  0     c  ):   # for each top vertex    for   x   in   range  (  0     3  ):   # for each bottom vertex    for   y   in   range  (  0     3  ):   # finding the third color of    # vertex either on right or left.    z   =   3   -   x   -   y   # finding area of triangle on    # left side of column.    if   (  x   !=   y   and   top  [  x  ][  i  ]   !=   INT_MAX   and   bottom  [  y  ][  i  ]   !=   INT_MIN   and   left  [  z  ]   !=   INT_MAX  ):   ans   =   max  (  ans     0.5   *   (  bottom  [  y  ][  i  ]   -   top  [  x  ][  i  ])   *   (  i   -   left  [  z  ]))   # finding area of triangle on right side of column.    if   (  x   !=   y   and   top  [  x  ][  i  ]   !=   INT_MAX   and   bottom  [  y  ][  i  ]   !=   INT_MIN   and   right  [  z  ]   !=   INT_MIN  ):   ans   =   max  (  ans     0.5   *   (  bottom  [  y  ][  i  ]   -   top  [  x  ][  i  ])   *   (  right  [  z  ]   -   i  ))   return   ans   # Precompute the vertices of top bottom left    # and right and then computing the maximum area.    def   maxarea  (  mat     r     c  ):   left   =   [  -  1  ]   *   3   right   =   [  0  ]   *   3   top   =   [[  -  1   for   i   in   range  (  C  )]   for   j   in   range  (  3  )]   bottom   =   [[  0   for   i   in   range  (  C  )]   for   j   in   range  (  3  )]   # finding the r b g cells for    # the left and right vertices.    for   i   in   range  (  0     r  ):   for   j   in   range  (  0     c  ):   left  [  mapcolor  (  mat  [  i  ][  j  ])]   =    min  (  left  [  mapcolor  (  mat  [  i  ][  j  ])]   j  )   right  [  mapcolor  (  mat  [  i  ][  j  ])]   =    max  (  left  [  mapcolor  (  mat  [  i  ][  j  ])]   j  )   # finding set of r g b of top    # and bottom for each column.    for   j   in   range  (  0     c  ):   for   i   in   range  (  0     r  ):   top  [  mapcolor  (  mat  [  i  ][  j  ])][  j  ]   =    min  (  top  [  mapcolor  (  mat  [  i  ][  j  ])][  j  ]   i  )   bottom  [  mapcolor  (  mat  [  i  ][  j  ])][  j  ]   =    max  (  bottom  [  mapcolor  (  mat  [  i  ][  j  ])][  j  ]   i  )   return   int  (  findarea  (  mat     R     C     top     bottom     left     right  ))   # Driver Code   if   __name__   ==   '__main__'  :   R     C   =   4     5   mat   =   [[  'r'     'r'     'r'     'r'     'r'  ]   [  'r'     'r'     'r'     'r'     'g'  ]   [  'r'     'r'     'r'     'r'     'r'  ]   [  'b'     'b'     'b'     'b'     'b'  ]]   INT_MAX     INT_MIN   =   float  (  'inf'  )   float  (  '-inf'  )   print  (  maxarea  (  mat     R     C  ))   # This code is contributed by Rituraj Jain   
  C#   
   // C# program to find maximum area of triangle   // having different vertex color in a matrix.   using     System  ;   class     MainClass     {      const     int     R     =     4  ;      const     int     C     =     5  ;      // return the color value so that their corresponding      // index can be access.      static     int     mapcolor  (  char     c  )      {      if     (  c     ==     'r'  )     {      return     0  ;      }      else     if     (  c     ==     'g'  )     {      return     1  ;      }      else     if     (  c     ==     'b'  )     {      return     2  ;      }      else     {      return     -  1  ;      }      }      // Returns the maximum area of triangle from all      // the possible triangles      static     double     findarea  (  char  [     ]     mat       int     r       int     c        int  [     ]     top       int  [     ]     bottom        int  []     left       int  []     right  )      {      double     ans     =     .  0  ;      // for each column      for     (  int     i     =     0  ;     i      <     c  ;     i  ++  )     {      // for each top vertex      for     (  int     x     =     0  ;     x      <     3  ;     x  ++  )     {      // for each bottom vertex      for     (  int     y     =     0  ;     y      <     3  ;     y  ++  )     {      // finding the third color of      // vertex either on right or left.      int     z     =     3     -     x     -     y  ;      // finding area of triangle on left side      // of column.      if     (  x     !=     y      &&     top  [  x       i  ]      !=     int  .  MaxValue  &&      bottom  [  y       i  ]      !=     int  .  MinValue  &&     left  [  z  ]      !=     int  .  MaxValue  )     {      ans     =     Math  .  Max  (      ans        (  1.0     /     2.0  )      *     (  bottom  [  y       i  ]     -     top  [  x       i  ])      *     (  i     -     left  [  z  ]));      }      // finding area of triangle on right      // side of column.      if     (  x     !=     y      &&     top  [  x       i  ]      !=     int  .  MaxValue  &&      bottom  [  y       i  ]      !=     int  .  MinValue  &&     right  [  z  ]      !=     int  .  MinValue  )     {      ans     =     Math  .  Max  (      ans        (  1.0     /     2.0  )      *     (  bottom  [  y       i  ]     -     top  [  x       i  ])      *     (  right  [  z  ]     -     i  )  +  4  );      }      }      }      }      return     ans  ;      }      // Precompute the vertices of top bottom left      // and right and then computing the maximum area.      static     double     maxarea  (  char  [     ]     mat       int     r       int     c  )      {      int  []     left      =     {     int  .  MaxValue       int  .  MaxValue       int  .  MaxValue     };      int  []     right      =     {     int  .  MinValue       int  .  MinValue       int  .  MinValue     };      int  [     ]     top     =     new     int  [  3       C  ];      int  [     ]     bottom     =     new     int  [  3       C  ];      // finding the r b g cells for the left      // and right vertices.      for     (  int     i     =     0  ;     i      <     r  ;     i  ++  )     {      for     (  int     j     =     0  ;     j      <     c  ;     j  ++  )     {      int     color     =     mapcolor  (  mat  [  i       j  ]);      if     (  color     !=     -  1  )     {      left  [  color  ]     =     Math  .  Min  (  left  [  color  ]     j  );      right  [  color  ]      =     Math  .  Max  (  right  [  color  ]     j  );      }      }      }      // finding set of {r g b} of top and      // bottom for each column.      for     (  int     j     =     0  ;     j      <     c  ;     j  ++  )     {      for     (  int     i     =     0  ;     i      <     r  ;     i  ++  )     {      int     color     =     mapcolor  (  mat  [  i       j  ]);      if     (  color     !=     -  1  )     {      top  [  color       j  ]      =     Math  .  Min  (  top  [  color       j  ]     i  );      bottom  [  color       j  ]      =     Math  .  Max  (  bottom  [  color       j  ]     i  );      }      }      }      return     findarea  (  mat       R       C       top       bottom       left        right  );      }      // Driven Program      public     static     void     Main  (  string  []     args  )      {      char  [     ]     mat     =     new     char  [     ]     {      {     'r'       'r'       'r'       'r'       'r'     }      {     'r'       'r'       'r'       'r'       'g'     }      {     'r'       'r'       'r'       'r'       'r'     }      {     'b'       'b'       'b'       'b'       'b'     }      };      Console  .  WriteLine  (  maxarea  (  mat       R       C  ));      }   }   
  JavaScript   
   // Javascript program to find maximum area of triangle   // having different vertex color in a matrix.   // return the color value so that their corresponding   // index can be accessed.   function     mapcolor  (  c  )     {      if     (  c     ==     'r'  )     return     0  ;      else     if     (  c     ==     'g'  )     return     1  ;      else     if     (  c     ==     'b'  )     return     2  ;   }   // Returns the maximum area of triangle from all   // the possible triangles   function     findarea  (  mat       r       c       top       bottom       left       right  )     {      let     ans     =     10  ;      // for each column      for     (  let     i     =     0  ;     i      <     c  ;     i  ++  )     {      // for each top vertex      for     (  let     x     =     0  ;     x      <     3  ;     x  ++  )     {      // for each bottom vertex      for     (  let     y     =     0  ;     y      <     3  ;     y  ++  )     {      // finding the third color of      // vertex either on right or left.      let     z     =     3     -     x     -     y  ;      // finding area of triangle on left side of column.      if     (  x     !=     y     &&     top  [  x  ][  i  ]     !=     Number  .  MAX_SAFE_INTEGER     &&      bottom  [  y  ][  i  ]     !=     Number  .  MIN_SAFE_INTEGER     &&      left  [  z  ]     !=     Number  .  MAX_SAFE_INTEGER  )     {      ans     =     Math  .  max  (  ans       (  1  /  2  )     *      (  bottom  [  y  ][  i  ]     -     top  [  x  ][  i  ])     *     (  i     -     left  [  z  ]));      }      // finding area of triangle on right side of column.      if     (  x     !=     y     &&     top  [  x  ][  i  ]     !=     Number  .  MAX_SAFE_INTEGER     &&      bottom  [  y  ][  i  ]     !=     Number  .  MIN_SAFE_INTEGER     &&      right  [  z  ]     !=     Number  .  MIN_SAFE_INTEGER  )     {      ans     =     Math  .  max  (  ans       (  1  /  2  )     *      (  bottom  [  y  ][  i  ]     -     top  [  x  ][  i  ])     *     (  right  [  z  ]     -     i  ));      }      }      }      }      return     ans  ;   }   // Precompute the vertices of top bottom left   // and right and then computing the maximum area.   function     maxarea  (  mat       r       c  )     {      let     left     =     [  Number  .  MAX_SAFE_INTEGER       Number  .  MAX_SAFE_INTEGER       Number  .  MAX_SAFE_INTEGER  ];      let     right     =     [  Number  .  MIN_SAFE_INTEGER       Number  .  MIN_SAFE_INTEGER       Number  .  MIN_SAFE_INTEGER  ];      let     top     =     Array  .  from  ({  length  :     3  }     ()     =>     Array  (  c  ).  fill  (  Number  .  MAX_SAFE_INTEGER  ));      let     bottom     =     Array  .  from  ({  length  :     3  }     ()     =>     Array  (  c  ).  fill  (  Number  .  MIN_SAFE_INTEGER  ));      // finding the r b g cells for the left      // and right vertices.      for     (  let     i     =     0  ;     i      <     r  ;     i  ++  )     {      for     (  let     j     =     0  ;     j      <     c  ;     j  ++  )     {      let     color     =     mapcolor  (  mat  [  i  ][  j  ]);      left  [  color  ]     =     Math  .  min  (  left  [  color  ]     j  );      right  [  color  ]     =     Math  .  max  (  right  [  color  ]     j  );      }      }      // finding set of {r g b} of top and      // bottom for each column.      for     (  let     j     =     0  ;     j      <     c  ;     j  ++  )     {      for     (  let     i     =     0  ;     i      <     r  ;     i  ++  )     {      let     color     =     mapcolor  (  mat  [  i  ][  j  ]);      top  [  color  ][  j  ]     =     Math  .  min  (  top  [  color  ][  j  ]     i  );      bottom  [  color  ][  j  ]     =     Math  .  max  (  bottom  [  color  ][  j  ]     i  );      }      }      return     findarea  (  mat       r       c       top       bottom       left       right  );   }   // Driven Program   const     R     =     4  ;   const     C     =     5  ;   const     mat     =     [      [  'r'       'r'       'r'       'r'       'r'  ]      [  'r'       'r'       'r'       'r'       'g'  ]      [  'r'       'r'       'r'       'r'       'r'  ]      [  'b'       'b'       'b'       'b'       'b'  ]   ];   console  .  log  (  maxarea  (  mat       R       C  ));   // akashish__   
   
    Sortir:       
  
 10  
  
    Complexité temporelle :    O(R*C)   
    Espace auxiliaire :    O(R+C)    
    Source:         https://stackoverflow.com/questions/40078660/maximum-area-of-triangle-having-all-vertices-of-différent-color     
    
         Créer un quiz