解題區/解題區 - Zerojudge

b314. 紅圓茵可的煩惱

contents

  1. 1. 內容 ：
  2. 2. 輸入說明 ：
  3. 3. 輸出說明 ：
  4. 4. 範例輸入 ：
  5. 5. 範例輸出 ：
  6. 6. Solution

內容 ：

相信大家都知道紅圓茵可是誰，就不多介紹了。最近他有一個煩惱，身為一位大魔法師，每天都有成千上萬的人來膜拜他<( )>。因為人數實在太多了，這麼多人跑到他家膜拜他，害他都無法好好練習魔法了。茵可家門前有一條柏油路，要到他家一定得經過這條柏油路，他決定把這條柏油路(長方形)切成N*M個格子，並且在其中某些格子設下陷阱，踩到陷阱的人會被傳送回柏油路的起點。「恩~這樣子就可以減少膜拜我的人了~」紅圓茵可心想。但是，為了讓jackyXX等人可以到達他家，也不能把柏油路封死，必須確保一定有條路徑可以走到茵可家。而你的任務是要提醒茵可大大<( )>，哪些點能放陷阱，而哪些點不能放陷阱(導致道路封死)。
柏油路的起點在左邊，而茵可家在柏油路的右邊。一個人在柏油路上只能往上下左右四個方向走，不能走斜對角。

一條3*10的柏油路

oooooooooo
oooooooooo
oooooooooo

一條被封死的柏油路

ooooxooooo
oooxoooooo
ooxooooooo

一條沒被封死的柏油路

xxxxxxoooo
oooooxoxxx
ooxxoooxoo

輸入說明 ：

第一行有3個正整數N、M、T，T為茵可接下來要放的陷阱數量(0<T<=N*M)。
接下來T行每行有2個非負整數x,y表示這個陷阱要放的位址。
縱軸為x軸，橫軸為y軸，左下角那格為(0,0)。
保證一個點只會被放最多一次。

測資

  1. N,M<=10
  2. N,M<=50
  3. N,M<=100
  4. N,M<=1000
  5. N,M<=1000

輸出說明 ：

對每一個要放的陷阱，若該點可放，請輸出一行”<( )>”(不含雙引號)，並且把陷阱放上去。
若該點不可放(會導致道路封死)，請輸出”>_<”(不含雙引號)，並且不放該陷阱。

範例輸入 ：

1
2
3
4
5
6
3 10 5
0 1
1 1
2 1
2 2
2 3

範例輸出 ：

1
2
3
4
5
<(_ _)>
<(_ _)>
>_<
>_<
<(_ _)>

Solution

這一題相當活用并查集的概念，雖然題目問說是否能左右相連，但是反過來則是上下邊界是否會從不相連變成相連。

多設兩個虛點，我們假想所有上界點都與虛上點相連，下界點都與虛下點相連，每次一次加入一個障礙物時，檢查九宮格內是否會造成上下虛點相連，這裡必須先偷看并查集的結果，隨後在考慮是否將其相連。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;
int parent[1048576], weight[1048576];
int used[1024][1024];
const int dx[] = {1, 1, 1, -1, -1, -1, 0, 0};
const int dy[] = {0, 1, -1, 0, 1, -1, 1, -1};
int findp(int x) {
    return parent[x] == x ? parent[x] : parent[x] = findp(parent[x]);
}
int joint(int p, int q) {
    p = findp(p), q = findp(q);
    if (weight[p] > weight[q])
        weight[p] += weight[q], parent[q] = p;
    else
        weight[q] += weight[p], parent[p] = q;
    return 1;
}
int main() {
    int n, m, Q, cases = 0;
    int x, y, tx, ty;
    while (scanf("%d %d %d", &n, &m, &Q) == 3) {
        cases++;
        int N = n * m + 10, up = n * m + 1, down = n * m + 2;
        int p, q, A[8];
        for (int i = 0; i < N; i++)
            parent[i] = i, weight[i] = 1;
        for (int i = 0; i < Q; i++) {
            scanf("%d %d", &x, &y);
            p = x * m + y;
            up = findp(up), down = findp(down);
            int s = 0;
            for (int j = 0; j < 8; j++)	{
                tx = x + dx[j], ty = y + dy[j];
                if (ty < 0 || ty >= m)	{
                    A[j] = p;
                    continue;
                }
                if (tx < 0)			q = up;
                else if(tx >= n)	q = down;
                else {
                    if (used[tx][ty] != cases) {
                        A[j] = p;
                        continue;
                    }
                    q = tx * m + ty;
                }
                if (findp(q) == up)		s |= 1;
                if (findp(q) == down)	s |= 2;
                A[j] = q;
            }
            if (s != 3) {
                puts("<(_ _)>");
                for (int j = 0; j < 8; j++) {
                    joint(p, A[j]);
                }
                used[x][y] = cases;
            } else {
                puts(">_<");
            }
        }
    }
    return 0;
}