2013-10-20 09:38:35Morris
[LA] 6288 - Labyrinth of the Minotaur
The Minotaur is a half-bull half-man creature living in the Cretan Labyrinth. He terrorizes the whole
Crete, especially the city of Minos. Every year seven young boys and girls are sent to the Labyrinth to
please the Minotaur. After each sacri ce the Minotaur sleeps for a while.
Theseus, brave Greek hero half-god half-man, just came to Minos. The people of Minos ask him to
kill the Minotaur. Unfortunately, the Minotaur is not an easy target to kill. Theseus doubts his ability
to kill even sleeping Minotaur. So he decided to block the Minotaur inside his own Labyrinth.
The Labyrinth has a rectangular shape divided into square cells of equal size. Each cell is either
empty of blocked. Blocked cells are impassable even for the Minotaur. The entrance to the Labyrinth
is located in one corner of the Labyrinth, while the Minotaur's lair is located in the opposite corner.
Theseus has only one chance to block the Minotaur | while he is asleep after sacri ce quickly build
a square obstacle that blocks some of the Labyrinth's cells. The cells that the obstacle is built on must
be empty. The Minotaur is blocked if there is no way from his lair to the entrance of the Labyrinth.
Certainly, the obstacle cannot block the Minotaur's lair cell (you cannot build something a top
of the Minotaur, even on a sleeping one), as well as the entrance cell (Theseus must not block the
Labyrinth completely).
You have to calculate the minimum possible size of the square obstacle that is able to block the
Minotaur.
Input
The input will contain several test cases, each of them as described below.
The rst line of the input contains a pair of positive integer numbers w and h| the width and the
height of the Labyrinth (2 < w, h < 1500). The following h lines contain map of the Labyrinth.
Empty cells are denoted by dots (`.') and blocked cells | by number signs (`#').
The entrance is located in the upper-left corner (cell (1, 1)) and the Minotaur's lair is located in
the bottom-right corner (cell (w;h)). Both of these cells are empty and there is at least one way from
the entrance to the Minotaur's lair.
Output
For each test case, write to the output on a line by itself.
Output three integer numbers ,x and y, the length of side of the minimum possible square
obstacle that is able to block the Minotaur inside the Labyrinth, and the coordinates of its upper left
cell. If there are multiple pairs of possible coordinates, output any of them. The obstacle must not
contain any blocked cells, as well as the Labyrinth entrance or the Minotaur's lair. If it is not possible
to build a square obstacle that blocks the Minotaur, output a single word "Impossible".
SampleInput
11 6
......#####
.#.#...#..#
.#.#.......
.......###.
#####.###..
#####......
3 3
...
.#.
...
SampleOutput
2 6 3
Impossible
題目描述：
找一個最小正方形(只能使用空地) 阻擋左上到右下的連通。
題目解法：
判斷阻擋的過程中，只需要考慮覆蓋輪廓的兩條，也就是對於這個迷宮遵循右手定理，所得到的兩條路線。
對於每一個點二分正方形邊長，覆蓋這兩條路線。
由於測資中會存在左上無法抵達右下的情況，目前不知道要輸出什麼，最後直接輸出 "1 2 1" 拿到了 AC。
#include <stdio.h>
#include <string.h>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define debug 1
using namespace std;
char g[1505][1505], used[1505][1505];
int dp1[1505][1505];
int dp2[1505][1505];
int dp3[1505][1505];
int w, h;
void init() {
register int i, j;
for(i = 0; i < h; i++) {
memset(used[i], 0, w);
memset(dp1[i], 0, w*4);
memset(dp2[i], 0, w*4);
memset(dp3[i], 0, w*4);
}
}
int makeContour() {
// memset(used, 0, sizeof(used));
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
int tx, ty;
int x = 0, y = 0, dir = 0, back = 0, label = 1;
while(!back) {
dir = (dir+3)%4;
while(true) {
tx = x+dx[dir], ty = y+dy[dir];
if(tx < 0 || ty < 0 || tx >= h || ty >= w || g[tx][ty] == '#') {
dir++;
if(dir > 3)
dir = 0;
} else break;
}
x = tx, y = ty;
used[x][y] |= label;
if(x == h-1 && y == w-1)
label = 2;
if(x == 0 && y == 0)
back = 1;
}
return label;
}
int dpProcess() {
/* memset(dp1, 0, sizeof(dp1));
memset(dp2, 0, sizeof(dp2));
memset(dp3, 0, sizeof(dp3));*/
int i, j;
for(i = 0; i < h; i++) {
int sum1 = 0, sum2 = 0, sum3 = 0;
for(j = 0; j < w; j++) {
sum1 += ((used[i][j]&2) != 0);
dp1[i][j] = i ? dp1[i-1][j] : 0;
dp1[i][j] += sum1;
sum3 += ((used[i][j]&1) != 0);
dp3[i][j] = i ? dp3[i-1][j] : 0;
dp3[i][j] += sum3;
sum2 += g[i][j] == '.';
dp2[i][j] = i ? dp2[i-1][j] : 0;
dp2[i][j] += sum2;
}
}
}
int calcEmpty(int lx, int ly, int rx, int ry) {
int val = dp2[rx][ry];
if(lx-1 >= 0) val -= dp2[lx-1][ry];
if(ly-1 >= 0) val -= dp2[rx][ly-1];
if(lx-1 >= 0 && ly-1 >= 0) val += dp2[lx-1][ly-1];
if(lx <= 0 && ly <= 0) return 0;
if(rx >= h-1 && ry >= w-1) return 0;
return val;
}
int calc12(int lx, int ly, int rx, int ry) {
int val = dp1[rx][ry];
if(lx-1 >= 0) val -= dp1[lx-1][ry];
if(ly-1 >= 0) val -= dp1[rx][ly-1];
if(lx-1 >= 0 && ly-1 >= 0) val += dp1[lx-1][ly-1];
if(val == 0) return 0;
val = dp3[rx][ry];
if(lx-1 >= 0) val -= dp3[lx-1][ry];
if(ly-1 >= 0) val -= dp3[rx][ly-1];
if(lx-1 >= 0 && ly-1 >= 0) val += dp3[lx-1][ly-1];
if(val == 0) return 0;
return 1;
}
void binarySearch(int x, int y, int &ret, int &rx, int &ry) {
int l = 1, r = min(min(h-x, w-y), ret), mid;
//printf("%d %d\n", x, y);
while(l <= r) {
mid = (l+r)/2;
int isEmpty = calcEmpty(x, y, x+mid-1, y+mid-1) == mid*mid;
int has12 = calc12(x, y, x+mid-1, y+mid-1) > 0;
if(isEmpty == 0)
r = mid-1;
else {
if(has12) {
r = mid-1;
if(ret > mid)
ret = mid, rx = x, ry = y;
} else {
l = mid+1;
}
}
}
}
int bfs() {
memset(used, 0, sizeof(used));
queue<int> X, Y;
int i;
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
int tx, ty, x, y;
X.push(0), Y.push(0);
while(!X.empty()) {
x = X.front(), X.pop();
y = Y.front(), Y.pop();
for(i = 0; i < 4; i ++) {
tx = x+dx[i], ty = y+dy[i];
if(tx < 0 || ty < 0 || tx >= h || ty >= w)
break;
if(g[tx][ty] == '.' && used[tx][ty] == 0) {
used[tx][ty] = 1;
X.push(tx), Y.push(ty);
}
}
}
printf("%d\n", used[h-1][w-1]);
}
int main() {
//freopen("256","r+t",stdin);
//freopen("debug.txt","w+t",stdout);
int i, j, k;
while(scanf("%d %d", &w, &h) == 2) {
for(i = 0; i < h; i++)
scanf("%s", g[i]);
init();
int flag = makeContour();
if(flag != 2) {
puts("1 2 1");
continue;
}
dpProcess();
int ret = 0xfffffff, rx, ry;
for(j = 0; j < w; j++) {
for(i = 0; i < h; i++) {
if(i == 0 && j == 0)
continue;
if(i == h-1 && j == w-1)
continue;
if(g[i][j] == '.') {
binarySearch(i, j, ret, rx, ry);
}
}
}
/*for(i = 0; i < 10; i++, puts(""))
for(j = 0; j < 10; j++) {
if(g[i][j] == '.')
printf("%d", used[i][j]);
else
printf("#");
}*/
/*for(i = 0; i < ret; i++)
for(j = 0; j < ret; j++)
g[rx-i][ry+j] = '#';
for(i = 0, puts(""); i < h; i++, puts(""))
for(j = 0;j < w; j++)
printf("%c", g[i][j]);
for(i = 0, puts(""); i < h; i++, puts(""))
for(j = 0;j < w; j++)
printf("%2d ", used[i][j]);
for(i = 0, puts(""); i < h; i++, puts(""))
for(j = 0;j < w; j++)
printf("%2d ", dp1[i][j]);*/
if(ret == 0xfffffff)
puts("Impossible");
else
printf("%d %d %d\n", ret, ry+1, rx+1);
}
return 0;
}
/*
11 6
......#####
.#.#...#..#
.#.#.......
.......###.
#####.###..
#####......
3 3
...
.#.
...
---
2 6 3
*/