Problem E - Bridge Building

Against the city's gleaming spires,
Above the ships that ply the stream,
A bridge of haunting beauty stands -
Fulfillment of an artist's dream
(D. B. Steinman)

Algorithm city is crossed by the beautiful Complexity River. Up until now, the only possible way to travel from one bank (margin) of the river to the other is by boat. This is very negative for the city economics and therefore the mayor has decided to build a series of bridges to connect the two parts of the city, lying on different banks of the river.

He has a fixed number of bridges to build, but in order to save the maximum amount of money he wishes to build the bridges has short as possible. However, since he wants to really help the citizens, the bridges must not be to close together, in order to have them splitted all over the city.

The mayor has asked for your help, and has given you the map of the part of city with that is near the river. To simplify, this map can be seen as a grid of chars. '#' means a piece of terrain and '.' means water. So, for example, a map could be something like:

####################
..######........##..
....##..............
....................
....................
.................#..
..######........##..
####################

Figure 1 - An example of a valid map

You can be sure that the map will always have terrain-only on the first and last rows, and that those pieces of terrain correspond to different banks. There will be no islands in the river, and all terrain will either be connected to the north or south bank. We consider a piece of terrain to be connected to another if they are adjacent, that is, if they are next to each other horizontally or vertically (but not diagonally). You can also be sure that on the same column of the grid map, there will never be a south piece of the bank above a north one. However, small lakes (that do not belong to the river) can exist inside banks, as exemplified in figure 2.

###############
.#..#.......#..
.####......##..
.####..........
.#........##...
..........#....
###############

Figure 2 - Another example of a valid map

The Algorithm City mayor is very old fashioned and has decided that the bridges to build must only be built in the north-south direction (vertically, in the grid). So, for example, imagine that the mayor would like to build 3 bridges, that must be separated at least by 4 positions, on the map of the figure 1. A solution that would minimize the length of the bridges would be the one in figure 3, where 'B' represents a bridge.

####################
..######........##..
..B.##.B.........B..
..B....B.........B..
..B....B.........B..
..B....B.........#..
..######........##..
####################

Figure 3 - A solution for the map of figure 1

Note that the first two bridges in the solution are exactly separated by 4 spaces as required, and could not be more close. If we measure the length of the bridges built by squares in the grid, we can say that the total length used was 11 (4+4+3). Any other way of building the bridges in this map would give more total length and therefore would be worse.

The Problem

Given a grid map as specified above, a number of bridges to build and the minimum space (on columns) that should separate the bridges, your task is to calculate the best positions to build the bridges in order to minimize their total length, and print the total length of the bridges in that best arrangement.

Input

The input file contains several test cases, each of them as describes below.

The first line of input contains two integers, R and C, representing respectively the numbers of rows and the number of columns of the grid map (5 ≤ R,C ≤ 1000).

Then comes a line with two integers, B and S, where B represents the number of bridges to build (1 ≤ B &le 100) and S the minimum space (in columns) that should separate bridges.

After that come exactly R lines, each one with C chars, that represent the map. This map obeys to the rules described above and only has '#' or '.'.

Output

For each test case, the output should contain a single line, with an integer representing the total length of bridges to build in the solution that minimizes this same total, as described above.

There will always be a way to build the bridges.

Sample Input

8 20
3 4
####################
..######........##..
....##..............
....................
....................
.................#..
..######........##..
####################
7 15
2 8
###############
.#..#.......#..
.####......##..
.####..........
.#........##...
..........#....
###############

Sample Output

11
2

---

2006 Programming Contest of Porto University
Round 3, 11th of October of 2006
 
(Author: Pedro Ribeiro - DCC/FCUP)

---

題目描述：

在一個 R*C 的地圖中，只有上(北)方陸地和下(南)方陸地，打算建造 B 座橋梁，

保證不會存在有北方陸地在南方陸地的南方，即不會有螺旋的樣子。

而每座橋梁只會筆直地由南到北，橋梁與橋梁之間至少間隔 S 格。

問最少成本(每座橋梁的長度總和)為何？

題目解法：

首先先找到每個位置的橋梁的最少成本。

然後 dp[i][j] 表示在位置 i 時，已經建造了 j 座橋梁。

此時 dp[i][j] = cost + min(dp[k][j-1]), 其中 k < i-S

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
char g[1005][1005], used[1005][1005];
int dp[1005][1005], supdp[1005];
int north[1005], south[1005];
int R, C, B, S;
void color(int x, int y, int flag) {
    queue<int> X, Y;
    int tx, ty, i;
    int dx[] = {0,0,1,-1};
    int dy[] = {1,-1,0,0};
    X.push(x), Y.push(y);
    while(!X.empty()) {
        x = X.front(), X.pop();
        y = Y.front(), Y.pop();
        if(flag)
            south[y] = min(south[y], x);
        else
            north[y] = max(north[y], x);
        for(i = 0; i < 4; i++) {
            tx = x+dx[i], ty = y+dy[i];
            if(tx < 0 || ty < 0 || tx >= R || ty >= C)
                continue;
            if(used[tx][ty] || g[tx][ty] == '.')
                continue;
            used[tx][ty] = 1;
            X.push(tx), Y.push(ty);
        }
    }
}
int main() {
    int i, j, k;
    while(scanf("%d %d %d %d", &R, &C, &B, &S) == 4) {
        for(i = 0; i < R; i++)
            scanf("%s", &g[i]);
        for(i = 0; i < C; i++)
            north[i] = -0xfffffff, south[i] = 0xfffffff;
        memset(used, 0, sizeof(used));
        for(i = 0; i <= B; i++)
            supdp[i] = 1000000000;
        color(0, 0, 0);
        color(R-1, 0, 1);
        supdp[0] = 0;
        for(i = 0; i < C; i++) {            
            if(i > S) {
                for(j = 1; j <= B; j++)
                    supdp[j] = min(supdp[j], dp[i-S-1][j]);
            }
            int cost = south[i]-north[i]-1;
            for(j = 1; j <= B; j++) {
                dp[i][j] = supdp[j-1]+cost;
            }
        }
        int ret = 0xfffffff;
        for(i = 0; i < C; i++)
            ret = min(ret, dp[i][B]);
        printf("%d\n", ret);
    }
    return 0;
}