Algoogle

Algorithm for Programming Contest

AOJ 1236 Map of Ninja House

Category: AOJ Tag: dfs, implementation

Map of Ninja House

問題概要


無向グラフ上をdfsで探索している.
未到達のノードに辿り着いた時, そのノードの次数をメモする.
到達済みのノードに来た時(戻ってくるのではなく)はそのノードの深さ-元いたノードの深さをメモする(必ず負になる).
今メモだけが残っている時, 元のグラフを復元しろ.

解法


dfsしていく.
新しいノードに入ったらidをつける.
また入力が負だった場合, 行き先の深さは一意に定まるのは明らか.
加えてdfsなのでまだ次元に余裕のある(辺の先が全て決まっていない)目的の深さのノードは自分の祖先しかありえず, 祖先の深さはユニークなので行き先も一意に定まる.

コード


(1236.cpp) download
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
#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i,a) repi(i,0,a)
int dim[128], door[128][64], cnt[128], depth[128];

void dfs(int &idx, int dep){
    int id = idx, nxt;
    depth[dep] = id;
    while(cnt[id] < dim[id]){
        cin >> nxt;
        if(nxt > 0) {
            door[id][cnt[id]++] = ++idx;
            door[idx][cnt[idx]++] = id;
            dim[idx] = nxt;
            dfs(idx, dep+1);
        }
        if(nxt < 0) {
            int nid = depth[nxt+dep];
            door[nid][cnt[nid]++] = id;
            door[id][cnt[id]++] = nid;
        }
    }
}

void solve(){
    memset(dim, -1, sizeof(dim));
    memset(door, -1, sizeof(door));
    memset(cnt, 0, sizeof(cnt));
    cin >> dim[0];
    int idx = 0;
    dfs(idx,0);
    cin >> cnt[0];
    rep(i,idx+1) {
        cout << i+1 << ' ';
        sort(door[i], door[i]+dim[i]);
        rep(j,dim[i]) cout << door[i][j]+1 << (j==dim[i]-1? '\n': ' ');
    }
}

signed main(){
    int T; cin >> T;
    while(T--) solve();
    return 0;
}

Comments