pass all test after 5 times submission...always struggling with brute force and trying to go a smart way. Finnaly, brute force wins.
Hope this could help for those who get stucked :). Sorry if my english sucks and the approach is not so optimal.
I think it is easier to solve this problem through table. First, set the BAD cell with -1. For the sample input :
6 6 BGBBGB GGGGGG BGBBGB GGGGGG BGBBGB BGBBGB
will be as -1 0 -1 -1 0 -1
0 0 0 0 0 0
-1 0 -1 -1 0 -1
0 0 0 0 0 0
-1 0 -1 -1 0 -1
-1 0 -1 -1 0 -1we know that it is impossible that the border has any pluses so we start from cell (1,1) until cell (row-1,col-1). In each cell we must find the distance from this cell to the blocked cell ( or border) in 4 directions : top, bottom, left, and right. Take the SMALLEST one and that will be the LENGTH of that cell to make the plus : length to the top, bottom, left, and right. That cell is the CENTER of a plus. The AREA from that plus is equal to (LENGTH*4)+1. From the sample input, the table is like :
-1 0 -1 -1 0 -1
0 1 0 0 1 0
-1 0 -1 -1 0 -1
0 1 0 0 1 0
-1 0 -1 -1 0 -1
-1 0 -1 -1 0 -1The cell with value 1 can make a plus with area of (1*4)+1=5
And now the Bruteforce time because we don't know which combination will have the biggest product. We assume that if we take a plus, that plus will block the cell and thus can't be used to make another plus...so recalculate the LENGTH from each cell. For example we find that the first cell (1,1) has LENGTH of 1. We assume that this is our FIRST PLUS that can create the maximal product and we need to find the other pair. But it can't be overlapped by the other plus. So first we blocked the cell
-1 -1 -1 -1 0 -1
-1 -1 -1 0 1 0
-1 -1 -1 -1 0 -1
0 1 0 0 1 0
-1 0 -1 -1 0 -1
-1 0 -1 -1 0 -1The table is now not valid anymore. So after recalculate using the same approach like the first time we get :
-1 -1 -1 -1 0 -1
-1 -1 -1 0 1 0
-1 -1 -1 -1 0 -1
0 0 0 0 1 0
-1 0 -1 -1 0 -1
-1 0 -1 -1 0 -1This is the second valid table and now we just need to search which one together with the FIRST PLUS could make the maximal product. In the table there are still 2 '1', so this 2 could result both (1*4)+1=5. Before we have plus with area of 5. So the maximal Area we got from the first try is 25. There are still 3 more tries : cell (3,1) as first plus, cell (1,4) as first plus, and cell (3,4) as first plus. Repeat the step to find the second plus. In this cases no matter if the first plus is (1,1) or (1,4) or (3,1) or (3,4), all give the maximal value of 25. So the biggest product is 25.
This approach seems to be so slow. But it can solve this problem which table has the maximal length of 12x12.
PS : For the most complex case with table 12x12 and all cell is good, the biggest product is 221 :)
After 7 submission finally got it =) My hint: 1) do not overlap pluses 2) you have to get the MAXIMUM PRODUCT so that it means getting MAXIMUM for 1 plus and getting MAXIMUM for 2 plus may not give you MAXIMUM PRODUCT
Finally Done.
Took lot of time.
My Java8 solution
public class Solution { static class Plus { int x; int y; int len; int size; Plus(int x, int y) { this.x = x; this.y = y; this.len = 0; this.size = 1; } Plus(int x, int y, int len, int size) { this.x = x; this.y = y; this.len = len; this.size = size; } void grow() { this.len++; this.size += 4; } boolean overlaps(Plus p2, int r, int c) { if(this.x != p2.x && this.y == p2.y) { if(p2.x >= this.x - this.len && p2.x <= this.x + this.len || p2.x < this.x - this.len && p2.x + p2.len >= this.x - this.len || p2.x > this.x + this.len && p2.x - p2.len <= this.x + this.len) return true; } if(this.y != p2.y && this.x == p2.x) { if(p2.y >= this.y - this.len && p2.y <= this.y + this.len || p2.y < this.y - this.len && p2.y + p2.len >= this.y - this.len || p2.y > this.y + this.len && p2.y - p2.len <= this.y + this.len) return true; } boolean[][] grid = new boolean[r][c]; for(int i = this.x - this.len; i <= this.x + this.len; i++) grid[this.y][i] = true; for(int i = this.y - this.len; i <= this.y + this.len; i++) grid[i][this.x] = true; for(int i = p2.x - p2.len; i <= p2.x + p2.len; i++) { if(grid[p2.y][i] == true) return true; } for(int i = p2.y - p2.len; i <= p2.y + p2.len; i++) { if(grid[i][p2.x] == true) return true; } return false; } } static void findPlus(int x, int y, int r, int c, String[] grid, ArrayList<Plus> list) { Plus plus = new Plus(x, y); int s = 1; while(y-s >= 0 && grid[y-s].charAt(x) != 'B' && y+s < r && grid[y+s].charAt(x) != 'B' && x-s >= 0 && grid[y].charAt(x-s) != 'B' && x+s < c && grid[y].charAt(x+s) != 'B') { list.add(new Plus(plus.x, plus.y, plus.len, plus.size)); plus.grow(); s++; } list.add(plus); } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int r = sc.nextInt(); int c = sc.nextInt(); sc.nextLine(); String[] grid = new String[r]; ArrayList<Plus> list = new ArrayList<Plus>(); for(int y = 0; y < r; y++) { grid[y] = sc.nextLine(); } for(int y = 0; y < r; y++) { for(int x = 0; x < c; x++) { if(grid[y].charAt(x) != 'B') findPlus(x, y, r, c, grid, list); } } int max = 0; for(int i = 0; i < list.size()-1; i++) { Plus p1 = list.get(i); for(int j = i+1; j < list.size(); j++) { Plus p2 = list.get(j); int sum = p1.size * p2.size; if(sum > max && !p1.overlaps(p2, r, c)) { max = sum; } } } System.out.println(max); } }
Sort 260 Discussions, By:
Please Login in order to post a comment