Algoogle

Algorithm for Programming Contest

AOJ 1245 Gap

Category: AOJ Tag: bfs

Gap

問題概要


初期状態が与えられて, はじめ1の位が1の数を昇順に一番左の列に置く.
空いているマスはその前のマスの数+1のものしか入らない.
空いているマスに数を移動させることを繰り返して全ての行が昇順にソートするときの最小ステップを求めよ.

解法


初期状態からBFSしていけばよい.

コード


(1245.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
#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,a) repi(i,0,a)
#define all(u) begin(u),end(u)
#define pb push_back
const int inf = 1e9;
const int w = 8;
string s;
map<string,int> d;

bool ok(string &t){
    rep(i,4) for(int j = 0; j < 2*(w-2); j+=2){
        int a = atoi(t.substr(2*w*i+j,2).c_str());
        int b = atoi(t.substr(2*w*i+j+2,2).c_str());
        if(!a or !b or b-a != 1) return 0;
    }
    return 1;
}

int solve(){
    queue<string> bfs;
    bfs.push(s);
    while(!bfs.empty()){
        string t = bfs.front(); bfs.pop();
        int td = d[t];
        if(ok(t)) return td;
        int cand[4] = {}, pos[4] = {}, idx = 0;
        rep(i,4) for(int j = 2; j < 2*w; j+=2){
            if(t[2*w*i+j] == '0'){
                cand[idx] = atoi(t.substr(2*w*i+(j-2),2).c_str())+1;
                pos[idx++] = 2*w*i+j;
            }
        }
        rep(i,4) for(int j = 2; j < 2*w; j+=2){
            int a = atoi(t.substr(2*w*i+j,2).c_str());
            rep(k,4) if(cand[k] == a){
                string nx = t;
                nx[pos[k]] = t[2*w*i+j];
                nx[pos[k]+1] = t[2*w*i+j+1];
                nx[2*w*i+j] = nx[2*w*i+j+1] = '0';
                if(!d.count(nx)){
                    d[nx] = td+1;
                    bfs.push(nx);
                }
                break;
            }
        }
    }

    return -1;
}

bool input(){
    s = "";
    d.clear();
    string t;
    rep(i,4){
        s.pb(i+1+'0');
        s.pb('1');
        rep(j,7) {
            cin >> t;
            if(t[1] != '1') s += t;
            else s += "00";
        }
    }
    return 0;
}
signed main(){
    int T; cin >> T;
    while(T--){
        input();
        cout << solve() << endl;
    }
    return 0;
}

Comments