We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
we 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 :
The 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
This 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 :)
Ema's Supercomputer
You are viewing a single comment's thread. Return to all comments →
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 -1
we 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 -1
The 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 -1
The 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 -1
This 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 :)