Algoogle

Algorithm for Programming Contest

AOJ 2223 Kaeru Jump

Category: AOJ Tag: brute-force, implementation

Kaeru Jump

問題概要


カエルが向いている方向の反対以外の方向の一番手前の葉っぱに移れる.
移る前の葉っぱはなくなる.
葉っぱが残り1枚になるまで移動するときの移動方向の列を求めよ.
ただし葉っぱは高々30枚で, 解は一意である.

解法


スタート地点から全探索する.

コード


(2223.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
#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)
#define pb push_back
int H, W, cnt;
char table[16][16];
const string dir = "URDL";
const int di[] = {-1,0,1,0}, dj[] = {0,1,0,-1};
inline bool in(int i, int j) { return i >= 0 and i < H and j >= 0 and j < W;}
string ans = "";

bool rec(int i, int j, int d, int res){
    table[i][j] = '.';
    if(!res) return 1;
    rep(k,3){
        int nd = (d+k+3)%4;
        int ni = i, nj = j;
        ans.pb(dir[nd]);
        while(in(ni,nj) and table[ni][nj] == '.')
            ni += di[nd], nj += dj[nd];
        if(in(ni,nj) and rec(ni,nj,nd,res-1)) return 1;
        ans.erase(ans.size()-1);
    }
    table[i][j] = 'o';
    return 0;
}
string solve(){
    rep(i,H)rep(j,W)
        if(dir.find(table[i][j]) != string::npos){
            rec(i,j,dir.find(table[i][j]),cnt);
            return ans;
        }
    return "";
}

void input(){
    cin >> H >> W;
    rep(i,H) rep(j,W){
        cin >> table[i][j];
        if(table[i][j] == 'o') cnt++;
    }
}
signed main(){
    input();
    cout << solve() << endl;
    return 0;
}

Comments