Circuit Routing
Time limit1sMemory limit128 MB
Find the minimum-cost grid path between two given cells where empty cells cost 1 and cells already occupied by given rectilinear circuits cost k, then output the path in compressed turn-point form.
- Level
Medium5 of 10
- Topics
- Shortest path, BFS, Matrix
- Solved
- No attempts yet
Problem
You need to place one new circuit on an n x n grid. Except at the boundary, each cell is adjacent to the four cells above, below, left, and right. A circuit is a path through adjacent cells, with a start cell and an end cell.
The grid already contains several circuits, and the two endpoints of the new circuit are given. The new circuit may pass through empty cells and may also pass through cells that already contain a circuit. Passing through an empty cell costs 1, and passing through a cell that already contains a circuit costs k. The costs of the start and end cells are included. Find a circuit whose total cell cost is as small as possible.
Input
The first line contains the grid size n. (1 <= n <= 50)
The second line contains four integers sr sc er ec, the row and column of the start cell and the row and column of the end cell of the new circuit. The two cells are different.
The third line contains k, the cost of passing through a cell that already contains a circuit. (2 <= k <= 60)
The fourth line contains m, the number of circuits already placed on the grid. (1 <= m <= 7)
Each of the next m lines describes one existing circuit. The first integer t is the number of points used to describe the circuit. (2 <= t <= 15) The remaining values are the start cell, the 90-degree turn cells, and the end cell in the form r1 c1 r2 c2 ... rt ct. Every two consecutive points are in the same row or the same column, and every cell on the segment between them already contains a circuit.
Output
On the first line, print the minimum cost of placing the new circuit.
On the second line, print one minimum-cost circuit in the same compressed format used for input circuits. First print the number of points t, followed by the start cell, all 90-degree turn cells, and the end cell, with each point written as row then column. The printed path must achieve the minimum cost from the first line.