After deciding to move in together, Xorin and Xoranna were faced with yet another problem. Their living room floor is a rectangular shaped grid, divided into n rows and m columns. The height of the room is h. Each square cell contains a stack of cube-shaped boxes. The appearance of the boxes from above and the positions of Xorin and Xoranna are shown in the example below (where n=7, m=5, h=4):
..... X ..... O ..#.. R .###. A .##.. N ..... N ..... A XORIN
Xorin is facing North (towards the Wall). He can see this:
..#.. ..##. .###. .###.
Xoranna is facing West. She can see this:
..#.... ..##... ..##... ..###..
Neither of the two is willing to start unpacking the boxes until they know the exact height of each stack. Your task is to find one possible set of heights that will attest to both their views, and also to the top view of the room.
Input
The first line of the input contains integers n, m, and h.The rest of the input contains 3 rectangular grids:
- the first grid has n rows and m columns, and depicts the top view of the room;
- the second grid has h rows and m columns, and depicts Xorin's view;
- the third and final grid has h rows and n columns, and depicts Xoranna's view.
Output
The output should contain a grid almost identical to the first input grid. The only difference between the two should be that each # symbol is replaced by a digit, describing the height of the stack located in that particular cell.
Constraints
- 1 ≤ n, m ≤ 1000
- 1 ≤ h ≤ 9
- 1 ≤ any stack's height ≤ h
- Any output that respects all three perspectives is considered correct.
- It is guaranteed that at least one valid solution exists.
Sample
| Input | Output |
|---|---|
| 7 5 4 ..... ..... ..#.. .###. .##.. ..... ..... ..#.. ..##. .###. .###. ..#.... ..##... ..##... ..###.. | ..... ..... ..1.. .213. .14.. ..... ..... |
Let's take a look at Xorin's perspective from left to right, and, for each column, calculate maxXorin[j] = the height of the stack Xorin sees. It is clear that Xorin will only see the tallest stack out of all those which lie on the same column.
The same idea applies for maxXoranna[i].
When attempting to reconstruct a possible solution, for each stack (i, j), two conditions must hold:
- stax[i][j] ≤ maxXorin[j]
- stax[i][j] ≤ maxXoranna[i]
In other words, the height of any stack must not exceed the height that Xorin sees, and the height that Xoranna sees.
However, this piece of information is incomplete. We also need to make sure that each column j (and line i) contains the value maxXorin[j] (and maxXoranna[i], respectively) at least once. To make sure this always happens, we can try a greedy approach: stax[i][j] = min(maxXorin[j], maxXoranna[i]), for each set of coordinates (i, j) that need to contain a stack.
Time complexity: O(n*m + n*h * m*h) ≈ O(n*m)
C++ solution (Sergiu Puscas)
1 #include <iostream> 2 #include <cstring> 3 #define nmax 1000 4 #define hmax 10 5 using namespace std; 6 7 int n, m, h, a[nmax][nmax], maxXorin[nmax], maxXoranna[nmax]; 8 string topView[nmax], XorinView[nmax], XorannaView[nmax], sol[nmax]; 9 10 int main() { 11 cin>>n>>m>>h; 12 cin.get(); 13 14 for(int i=0; i<n; i++) getline(cin, topView[i]), sol[i].resize(m, '.'); 15 for(int i=0; i<h; i++) { 16 getline(cin, XorinView[i]); 17 for(int j=0; j<m; j++) 18 if(XorinView[i][j] == '#' && maxXorin[j] == 0) maxXorin[j] = h-i; 19 } 20 21 for(int i=0; i<h; i++) { 22 getline(cin, XorannaView[i]); 23 for(int j=0; j<n; j++) 24 if(XorannaView[i][j] == '#' && maxXoranna[n-j-1] == 0) maxXoranna[n-j-1] = h-i; 25 } 26 27 for(int i=0; i<n; i++) 28 for(int j=0; j<m; j++) 29 if(topView[i][j] == '#') 30 sol[i][j] = '0' + min(maxXorin[j], maxXoranna[i]); 31 32 for(int i=0; i<n; i++) cout<<sol[i]<<"\n"; 33 return 0; 34 } 35
