레이팅 미적용You are an employee of the Brussels Architectural Projects Consultancy in charge of ensuring all building designs meet the accessibility requirements. As law dictates, every part of your building should be reachable for wheelchair users, which means elevators will have to be installed. You are given the blueprints of the company's current project and have to determine the minimum number of elevators required.
The floor plan is laid out on a square grid and the blueprints tell you the number of floors above any given square. You can place an elevator at any square, which stops at all floors of that square. A wheelchair user can move up and down between floors using the elevators and can freely move to any of the four adjacent squares on the same floor. Buildings do not connect diagonally.
Figure shows the second sample input. Designs can consist of multiple buildings; this one contains three buildings. The design requires two elevators: one for the pyramid-shaped building and one for the tall tower. The small building of height one does not require an elevator, since it only has a ground floor.
The input consists of:
- One line containing integers \(h\) and \(w\) (\(1\leq h, w\leq 500\)), the height and width of the grid.
- \(h\) lines of \(w\) integers each, where \(x_{i,j}\) (\(0\leq x_{i,j} \leq 10^9\)), the \(j\)th integer on the \(i\)th line, denotes the number of floors at position \((i,j)\) of the grid.
Output the minimum number of elevators you need to build to be able to reach every part of the building(s) in the grid.
3 3
1 2 3
0 0 4
7 6 5
1
6 7
0 0 0 0 0 0 0
0 1 2 3 2 1 0
0 1 2 3 2 1 0
0 0 0 0 0 0 0
0 1 0 5 0 0 0
0 0 0 0 0 0 0
2
4 4
1 1 2 1
2 2 1 2
1 2 2 1
2 1 2 2
4