[ACM-ICPC][搜索] 5729 - Coalescing Continents
Continental drift refers to the idea that once the
earth’s continents were all in one piece and with time they drifted away from
each other and arrived at their present positions.
In this problem, we are concerned with the reverse process – Continental Coalesce.
For the sake of brevity, let’s assume the continents were initially merged together forming a square. With time, the square disintegrated into K different continents in the shape of rectangles and drifted away from its source.
You are provided with the current locations of the continents (i.e. rectangles). These locations were outlined with the help of satellites. Your first job is to figure out whether the data provided is a valid one. The data is valid if you can move the rectangles and form a square. In one move, you can pick any rectangle and push it one unit in one of the four directions (north, south, east or west). The continents can slide underneath one another during movement – meaning, more than one continent can occupy a particular position simultaneously. If it is possible to form a square then you are also required to find the minimum number of moves to do that. The final position of the square is not the primary concern here. Note that in the final position, two continents cannot overlap and the desired square cannot have any holes in it.
Input
The first line of input is an integer T (T <= 200) that indicates the number of test cases. Each case consists of 20 lines containing 20 characters. Each character can either be a dot(.) representing an empty space or an x (ASCII value 120). Every x character will be part of some continent.
Notes:
· In the input grid, it’s guaranteed that, x characters from different continents will not be adjacent to each other. Any x character will be part of some rectangle
· Two cells are adjacent if they share a common edge.
· There will be exactly 25 x characters in the grid.
· The number of continents, K, will be at most 5.
· There is a blank line before the start of every case.
· The rectangles and the desired square are axis parallel.
· The earth here is flat. That is, the first and last row is NOT adjacent to each other. Same thing holds for the first and last column.
Output
For each case, output the case number first. If it’s not possible to form a square by moving the rectangles around, output “invalid data”, quotes for clarity. If it is possible, output the minimum number of moves required to complete the task.
|
Sample Input |
Sample Output |
|
2
.................... .................... .................... .................... .................... .................... ..xxxxx............. ..xxxxx............. .................... .................... ..xx..........xxx... .................... ..xxxxx............. ..xxxxx............. .................... .................... .................... .................... .................... ....................
.................x.. .................... .................... .................... ..xx................ ..xx................ ..xx................ ..xx................ ..xx................ ..xx................ .......xxxxxx....... .......xxxxxx....... .................... .................... .................... .................... .................... .................... .................... ....................
|
Case 1: 13 Case 2: invalid data |
先拼成 5x5 的，接著窮舉所在位置，然後用平移計算即可。
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <stdlib.h>
using namespace std;
struct {
int x, y, a, b;
} cont[5];
char gcont[5][5] = {};
int m, contused[5] = {};
int check(int idx, int tx, int ty) {
if(tx+cont[idx].a > 5 || ty+cont[idx].b > 5)
return 0;
int i, j;
for(i = tx; i < tx+cont[idx].a; i++) {
for(j = ty; j < ty+cont[idx].b; j++) {
if(gcont[i][j])
return 0;
}
}
return 1;
}
int contx[5], conty[5];
int ans;
void dfs(int idx) {
int tx, ty, i, j, k;
if(idx == m) {
for(i = 0; i <= 15; i++) {
for(j = 0; j <= 15; j++) {
int tmp = 0;
for(k = 0; k < m; k++) {
tmp += abs(i+contx[k]-cont[k].x)+abs(j+conty[k]-cont[k].y);
}
if(tmp < ans)
ans = tmp;
}
}
return;
}
for(i = 0; i < 5; i++) {
for(j = 0; j < 5; j++) {
if(gcont[i][j] == 0) {
tx = i, ty = j;
break;
}
}
if(j != 5) break;
}
for(i = 0; i < m; i++) {
if(contused[i] == 0 && check(i, tx, ty)) {
contused[i] = 1;
for(j = tx; j < tx+cont[i].a; j++)
for(k = ty; k < ty+cont[i].b; k++)
gcont[j][k] = i+1;
contx[i] = tx, conty[i] = ty;
dfs(idx+1);
for(j = tx; j < tx+cont[i].a; j++)
for(k = ty; k < ty+cont[i].b; k++)
gcont[j][k] = 0;
contused[i] = 0;
}
}
}
int main() {
int t;
int cases = 0;
scanf("%d", &t);
while(t--) {
char g[31][31];
int i, j, hi, hj;
m = 0;
for(i = 0; i < 20; i++)
scanf("%s", g[i]);
int used[31][31] = {}, a, b;
for(i = 0; i < 20; i++) {
for(j = 0; j < 20; j++) {
if(g[i][j] == 'x' && used[i][j] == 0) {
a = 0, b = 0;
while(g[i+a][j] == 'x') a++;
while(g[i][j+b] == 'x') b++;
for(hi = 0; hi < a; hi++)
for(hj = 0; hj < b; hj++)
used[i+hi][j+hj] = 1;
cont[m].x = i, cont[m].y = j;
cont[m].a = a, cont[m].b = b;
m++;
}
}
}
ans = 2147483647;
dfs(0);
printf("Case %d: ", ++cases);
if(ans == 2147483647)
cout << "invalid data" << endl;
else {
cout << ans << endl;
}
}
return 0;
}