Adott egy mátrix N sorok és M oszlop három {r g b} értékből áll. A feladat annak a legnagyobb háromszögnek a területe, amelynek az egyik oldala párhuzamos az y tengellyel, azaz függőleges, és mindhárom csúcs színe eltérő.
Példák:
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.
Tudjuk, hogy egy háromszög területe = 1/2 * alap *magasság, ezért maximalizálnunk kell a háromszög alapját és magasságát. Mivel az egyik oldal párhuzamos az y tengellyel, ezt az oldalt tekinthetjük a háromszög alapjának.
A bázis maximalizálása érdekében minden oszlophoz megtaláljuk az {r g b} első és utolsó előfordulását. Tehát minden oszlophoz két 3 értékből álló halmazunk van. Bármely oszlop bázisához az egyik csúcs az első halmazból, a második pedig a második halmazból származik, így ezek eltérő értékkel rendelkeznek.
Bármely oszlop magasságának maximalizálásához alapként a harmadik csúcsot úgy kell megválasztani, hogy a csúcs legyen a legtávolabb az oszlop bal vagy jobb oldalán lévő oszloptól, amelynek értéke eltér a másik két csúcstól.
Most minden oszlophoz keresse meg a háromszög maximális területét.
Az alábbiakban bemutatjuk ennek a megközelítésnek a megvalósítását:
C++
// C++ program to find maximum area of triangle // having different vertex color in a matrix. #include
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 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# 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 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__
Kimenet:
10
Időbeli összetettség: O(R*C)
Kiegészítő tér: O(R + C)
Forrás: https://stackoverflow.com/questions/40078660/maximum-area-of-triangle-having-all-vertices-of-different-color