Algoogle

Algorithm for Programming Contest

AOJ 1251 Pathological Paths

Category: AOJ Tag: parsing

Pathological Paths

問題概要


解法


調べるパスの途中に知らないディレクトリがあったらnot found
“..”とか”.”の処理をしてindex.htmlを適切につけたものが, 最初N個になかったらnot found
それ以外で2つが一致したらyes
それ以外はno

コード


(1251.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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <bits/stdc++.h>
#define repi(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,a) repi(i,0,a)
#define pb push_back
using namespace std;

int N, M;
set<string> urls;
set<string> dirs;

void normalize(string &url){
    vector<string> dir;
    string hoge = "";
    rep(i,url.size()){
        if(url[i] == '/'){
            if(hoge == ".."){
                if(dir.size() == 0){
                    url = "";
                    return;
                }
                dir.pop_back();
            }
            else if(hoge != "."){
                if(hoge == "") continue;
                dir.pb(hoge);
                string tmp = "";
                rep(j,dir.size()){
                    tmp += "/";
                    tmp += dir[j];
                }
                if(dirs.find(tmp) == dirs.end()){
                    url = "";
                    return;
                }
            }
            hoge = "";
        }
        else hoge += url[i];
    }
    if(hoge == "..") {
        if(dir.size() == 0){
            url = "";
            return;
        }
        dir.pop_back();
    }
    else if(hoge != "." && hoge != "") dir.pb(hoge);
    url = "";
    rep(i,dir.size()) {
        url += "/";
        url += dir[i];
    }
    if(dirs.find(url) != dirs.end()){
        url += "/index.html";
    }
    if(url == "") url = "/index.html";
    return;
}

int main(){
    int cnt = 0;
    while(cin >> N >> M, N || M){
        urls.clear();
        dirs.clear();
        while(N--){
            string str; cin >> str;
            urls.insert(str);
            string dir = "";
            string hoge = "/";
            repi(i,1,str.size()){
                if(str[i]=='/') {
                    dir += hoge;
                    dirs.insert(dir);
                    hoge = "/";
                }
                else hoge += str[i];
            }
        }
        while(M--){
            string a, b;
            cin >> a >> b;
            normalize(a); normalize(b);
            cerr << "Case " << cnt++ << ": " << a << ' ' << b << endl;
            if(a == "" || b == "" || urls.find(a) == urls.end() || urls.find(b) == urls.end())
                cout << "not found\n";
            else if(a == b) cout << "yes\n";
            else cout << "no\n";
        }
    }
    return 0;
}

Comments