Algoogle

Algorithm for Programming Contest

AOJ 2342 Light Road

Category: AOJ Tag: dijkstra

Light Road

問題概要


下向きにレーザーを発射して, 鏡に反射させることで敵を倒したい.
「/」のむきの鏡と「\」の向きの両面鏡がそれぞれA枚あるので敵を倒すための最小の設置数を求めよ.
ただし壁と鏡は貫通できず, 不可能な場合は-1を出力しろ.

解法


現在位置と使った鏡の枚数, 入ってきた向きを状態としてDijkstraする.
ただし鏡をレーザーの位置に置いたり, レーザーの位置を縦に貫通する場合は無視すること.
縦に貫通する場合は初期と同じだし, 鏡をレーザーの位置に置くと初期の状態に矛盾するため.

コード


(2342.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
#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 pb push_back
const int di[] = {-1,0,1,0};
const int dj[] = {0,1,0,-1};
struct node{
    int i, j, p, q, dir, dis;
    bool operator<(const node &n) const{ return dis > n.dis;}
};
int N, M, A, si, sj, ti, tj;
bool room[128][128];
int dist[101][101][11][11][4];
inline bool in(int i, int j){ return i >= 0 and j >= 0 and i < N and j < M;}

int solve(){
    memset(dist,-1,sizeof(dist));
    priority_queue<node> que;
    que.push((node){si,sj,0,0,2,0});
    while(!que.empty()){
        node v = que.top(); que.pop();
        if(v.i == ti and v.j == tj) return v.dis;
        if(dist[v.i][v.j][v.p][v.q][v.dir] >= 0) continue;
        dist[v.i][v.j][v.p][v.q][v.dir] = v.dis;
        rep(nd,3){
            int d = (v.dir+nd+3)%4;
            if(v.i == si and v.j == sj and v.dis and di[d]) continue;
            if(v.i == si and v.j == sj and v.dir != d) continue;
            bool isp = (v.dir+d)==3;
            bool isq = (v.dir+d)%4==1;
            if(isp and v.p >= A) continue;
            if(isq and v.q >= A) continue;
            int i = v.i+di[d], j = v.j+dj[d];
            if(in(i,j) and room[i][j])
                que.push((node){i,j,v.p+isp,v.q+isq,d,v.dis+isp+isq});
        }
    }
    return -1;
}

void input(){
    cin >> N >> M >> A;
    rep(i,N) rep(j,M){
        char c; cin >> c;
        room[i][j] = 1;
        if(c == 'S') si = i, sj = j;
        else if(c == 'G') ti = i, tj = j;
        else if(c == '#') room[i][j] = 0;
    }
}
signed main(){
    input();
    cout << solve() << endl;
    return 0;
}

Comments