Algoogle

Algorithm for Programming Contest

Codeforces 382D Ksenia and Pawns

Category: Codeforces Tag: dfs, tree

Ksenia and Pawns

問題概要


盤上に向きが指定されているマスがある.
コマを2つ置いてそのマスの指示通りに動かす(何も書かれていないマスで止まる).
向きが指定されているマスには同時に2つのコマは置けず, そうでないマスには置ける.
移動後に同時に2コマ存在することになる場合はそこで終了.
2つのコマの位置を決めるとき, 動く回数の総和を最大はいくらになるか. 無限に移動できる場合は-1を出力しろ

解法


移動のルートは無限ループを除いて, ‘#’を根とする木になっている.
根には2つのコマがきてもいいので, その子の部分木を考える.
各部分木の高さhを求めれば最長距離がわかり, その木に2つ置く場合はh-1が2番目に長い距離になる(高さhが2つ以上存在する場合でもそれは途中でぶつかる).
あとはこれを全ての’#’を根とする木について調べて高さの最大2つを取ってくれば良い.

コード


(382D.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
#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)
const int MAX = 2001;
typedef pair<int,int> pii;
const int di[] = {-1,0,1,0};
const int dj[] = {0,-1,0,1};
const string dir = "v>^<";

char b[MAX][MAX];
int H, W, done;
inline bool in(int i, int j){ return i>=0 and i<H and j>=0 and j<W;}

int dfs(int i, int j, int dep){
    done++;
    int ret = dep;
    rep(d,4){
        int ni = i + di[d], nj = j + dj[d];
        if(in(ni,nj) and b[ni][nj] == dir[d])
            ret = max(ret, dfs(ni,nj,dep+1));
    }
    return ret;
}

int solve(){
    int u = 0, v = 0;
    rep(i,H)rep(j,W)
        if(b[i][j] == '#'){
            done++;
            rep(d,4){
                int ni = i + di[d], nj = j + dj[d];
                if(in(ni,nj) and b[ni][nj] == dir[d]){
                    int t = dfs(ni,nj,1);
                    if(u < t) u = t, v = t-1;
                    else if(v < t) v = t;
                }
            }
        }
    return done<H*W? -1: u + v;
}

void input(){
    cin >> H >> W;
    rep(i,H)rep(j,W) cin >> b[i][j];
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    input();
    cout << solve() << endl;
    return 0;
}

Comments