Algoogle

Algorithm for Programming Contest

AOJ 2302 On or Off

Category: AOJ Tag: implementation

On or Off

問題概要


R*Cのエリアに部屋と壁がある. 各部屋から部屋へのパスは一意に定まる.
M個のタスクが与えられ, それぞれ決められた部屋に行かなければならない.
各部屋は始め電気がついていなく, 部屋を通るときは電気を付けなければならない.
また最後のタスク終了時には全ての部屋の電気が消えている必要がある.
各部屋の電気のon/offのコストと, 付いている時の時間あたりのコストが与えられるとき, 最小のコストを求めよ.

解法


パスが一意に定まるので各部屋を通る時刻を列挙する.
あとは前回来た時の時刻と比較してつけっぱなしがいいか, 消してつけるほうがいいか決める.

コード


(2302.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 pb push_back

typedef pair<int,int> pii;
const int dr[] = {-1,0,1,0};
const int dc[] = {0,1,0,-1};
int R, C, M, t;
bool room[64][64], checked[64][64];
int cst[4][64][64];
pii task[1024];
vector<int> visit[64][64];

inline bool in(int &r, int &c){ return r >= 0 and r < R and c >= 0 and c < C;}

int dfs(int r, int c, int i, int d){
    if(r == task[i].first and c == task[i].second){
        return d;
    }
    rep(k,4){
        int nr = r + dr[k], nc = c + dc[k];
        if(in(nr,nc) and room[nr][nc] and !checked[nr][nc]){
            checked[nr][nc] = 1;
            int ret = dfs(nr,nc,i,d+1);
            checked[nr][nc] = 0;
            if(ret){
                visit[r][c].pb(t+d);
                return ret;
            }
        }
    }
    return 0;
}

int solve(){
    int r = task[0].first, c = task[0].second;
    t = 0;
    repi(i,1,M){
        checked[r][c] = 1;
        int d = dfs(r,c,i,0);
        checked[r][c] = 0;
        r = task[i].first;
        c = task[i].second;
        t += d;
    }
    visit[r][c].pb(t);
    int ans = 0;
    rep(r,R)rep(c,C) if(room[r][c]){
        vector<int> &v = visit[r][c];
        if(visit[r][c].size() == 0) continue;
        ans += cst[1][r][c] + cst[2][r][c]; // first in last out
        rep(i,v.size()-1){
            if((v[i+1]-v[i])*cst[0][r][c] > cst[1][r][c] + cst[2][r][c])
                ans += cst[1][r][c] + cst[2][r][c];
            else ans += (v[i+1]-v[i]) * cst[0][r][c];
        }
    }
    return ans;
}

void input(){
    cin >> R >> C >> M;
    rep(i,R)rep(j,C){
        char c; cin >> c;
        room[i][j] = (c == '.');
    }
    rep(k,3)rep(i,R)rep(j,C) cin >> cst[k][i][j];
    rep(i,M) cin >> task[i].first >> task[i].second;
}
int main(){
    input();
    cout << solve() << endl;
    return 0;
}

Comments