[UVA][dp] 10888 - Warehouse
Problem B
Warehouse
Input: Standard Input
Output: Standard Output
A number of boxes is to be moved in a warehouse. The warehouse can be modeled as a grid where each square is the equal to the size of a box. Consider the model below: (‘B’ = box to be moved, ‘.’ = empty square, ‘X’ = position a box should occupy after the move, ‘#’ = obstacle)
BBBB.....###...X.XX#...X...#............
A box may be moved to any of its four neighboring squares, assuming this square is empty (that is, not occupied by another box or an obstacle). To move a box takes one unit of time, and only one box may be moved per time unit. Your task is to determine the least amount of time to move all boxes to their destination squares. You may assume that a solution exists. Number of boxes will be no more than 15.
Input
The first line in the input contains the number of test cases (at most 20). Each case starts with a line containing two integers, the height (1 ≤ h ≤ 40) and width (1 ≤ w ≤ 40) of the grid. Then follows h lines, each containing w characters, describing the grid in the format above.
Output
For each test case, output a line containing a single integer: the minimum number of time units to move all boxes.
Sample Input Output for Sample Input
15 8BBBB.....###...X.XX#...X...#............ |
20 |
Problem setter: Jimmy Mårdell
Special Thanks: Mohammad Sajjad Hossain
test case:
5
5 8
BBBB....
.###...X
.XX#...X
...#....
........
5 8
....#...
....#...
B..X#B.X
....#...
....#...
題目簡單地要求二分圖匹配權重總合最小。
位元的狀態壓縮，把已經匹配過的點當做1, 沒有則0, 因此最多 15 bits。
dp 的方法：
依序放入X團的點，然後Y團匹配過的會變成一個狀態，從狀態中沒被匹配過的點進行鬆弛。
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
int ng[50][50], used[50][50];
int dp[1<<16], W[30][30];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
int Bt, Xt, n, m;
char g[50][50];
void bfs(int x, int y) {
memset(used, 0, sizeof(used));
int i, tx, ty;
queue<int> X, Y;
X.push(x), Y.push(y);
while(!X.empty()) {
x = X.front(), X.pop();
y = Y.front(), Y.pop();
if(g[x][y] == 'X')
W[Bt][ng[x][y]] = used[x][y];
for(i = 0; i < 4; i++) {
tx = x+dx[i], ty = y+dy[i];
if(tx < 0 || tx >= n || ty < 0 || ty >= m)
continue;
if(g[tx][ty] == '#')
continue;
if(used[tx][ty] == 0) {
used[tx][ty] = used[x][y]+1;
X.push(tx);
Y.push(ty);
}
}
}
}
int main() {
int t, i, j, k;
scanf("%d", &t);
while(t--) {
scanf("%d %d", &n, &m);
for(i = 0; i < n; i++)
scanf("%s", g[i]);
Bt = 0, Xt = 0;
for(i = 0; i < n; i++)
for(j = 0; j < m; j++)
if(g[i][j] == 'X')
ng[i][j] = Xt++;
for(i = 0; i <= Xt; i++)
for(j = 0; j <= Xt; j++)
W[i][j] = 1<<20;
for(i = 0; i < n; i++) {
for(j = 0; j < m; j++) {
if(g[i][j] == 'B') {
Bt++;
bfs(i, j);
}
}
}
int mxState = (1<<Xt);
for(i = 0; i < mxState; i++)
dp[i] = 1<<20;
dp[0] = 0;
vector<int> DIGIT[16];
for(i = 0; i < mxState; i++) {
j = __builtin_popcount(i);
DIGIT[j].push_back(i);
}
for(i = 1; i <= Bt; i++) {
for(int k1 = 0; k1 < DIGIT[i-1].size(); k1++) {
j = DIGIT[i-1][k1];
for(k = 0; k < Bt; k++) {
if((j&(1<<k)) == 0) {
dp[j|(1<<k)] = min(dp[j|(1<<k)], dp[j]+W[i][k]);
}
}
}
}
printf("%d\n", dp[mxState-1]);
}
return 0;
}
/*
5
5 8
BBBB....
.###...X
.XX#...X
...#....
........
5 8
....#...
....#...
B..X#B.X
....#...
....#...
*/
這題有可能'X'的數目允許比'B'的數目多嗎?
不然最好使用 min-cost-maxflow, 最少費用流。 2013-04-23 11:36:03