AOJ 2302 On or Off - arrows blog

問題概要

RxCのグリッドがある。グリッドは、'.' (部屋)または'#'(壁)で構成されており、壁には侵入することができない。

人は上下左右の部屋に移動することができ、移動するには1単位時間かかる。

全ての部屋には、電気がついており、部屋に入るためには電気をつけなければならない。
しかし、部屋を出る際には必ずしも消す必要はなく、つけっ放しにすることもできる。

それぞれの部屋の、電気をつけっ放しにしたときの1単位時間毎にかかる電気代、電気をつけるための電気代、電気を消すための電気代がある。

今、M個の仕事を遂行したいと思っている。それぞれの仕事iは、部屋(xi, yi)で行う必要がある。
ただし、仕事は入力で与えられた順番に遂行しなければならない。

このとき、全ての仕事を遂行したときにかかる電気代を最小化せよ。ただし、最終的に全ての部屋の電気を消す必要がある。

※ スタート位置は、仕事1の部屋から。

制約

1 ≤ R ≤ 50
1 ≤ C ≤ 50
2 ≤ M ≤ 1000

解法

BFS + Greedy

まず、それぞれの仕事をする部屋の間の最短経路をBFS等で求め、同時に経路復元をする。
そして、それらを元に、あるマス(x, y)を何回訪れるかとそこを訪れるときの時刻をメモする。

ここからコスト計算。
まず、任意の部屋において、入る際には電気をつけなければならない。かつ、最終的に電気が消えていないといけない。
という条件から、ある部屋を訪れるには、その部屋の電気をつけて、消すためのコストは必ずかかる。

次に、ある部屋(x,y)を複数回訪れる場合、i回目に部屋を訪れたときからi+1回目に部屋を訪れたときの間について電気をつけっ放しにするか、一旦電気を消して再び訪れたときに付けるかを選択しなければならない。
これは、電気をつけっ放しにするコストx(i+1回目に部屋に訪れるときの時刻-i回目に部屋に訪れるときの時刻) と電気をつけるコストと消すコストの和の小さい方を選択する。

これを全ての移動マスについてやると答えが求まる。

コード

#include <bits/stdc++.h>
 
using namespace std;
 
#define MAX_R 50
#define MAX_C 50
#define INF (1<<29)
typedef pair<int, int> pii;
 
bool inField(int x, int y, int C, int R)
{
    return (0 <= x && x < C && 0 <= y && y < R);
}
 
int main()
{
    int R, C, M;
    char field[MAX_R][MAX_C];
    cin >> R >> C >> M;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> field[i][j];
        }
    }
    int cost[3][MAX_R][MAX_C];
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < R; j++) {
            for (int k = 0; k < C; k++) {
                cin >> cost[i][j][k];
            }
        }
    }
    vector<int> X(M), Y(M);
    for (int i = 0; i < M; i++) {
        cin >> Y[i] >> X[i];
    }
 
    const int dx[] = {-1, 0, 1, 0};
    const int dy[] = {0, -1, 0, 1};
     
    map<pii, vector<int>> vis;
    int prev_d = 0;
    for (int i = 1; i < M; i++) {
        queue<pii> Q; Q.push(pii(X[i-1], Y[i-1]));
        vector<vector<int>> d(MAX_R, vector<int>(MAX_C, INF));
        vector<vector<int>> prev(MAX_R, vector<int>(MAX_C, INF));
        d[Y[i-1]][X[i-1]] = prev_d;
        while (!Q.empty()) {
            pii p = Q.front(); Q.pop();
            int x = p.first, y = p.second;
            if (x == X[i] && y == Y[i]) {
                prev_d = d[y][x];
                break;
            }
            for (int j = 0; j < 4; j++) {
                int nx = x + dx[j], ny = y + dy[j];
                if (!inField(nx, ny, C, R) ||
                    field[ny][nx] == '#') {
                    continue;
                }
                if (d[y][x] + 1 < d[ny][nx]) {
                    d[ny][nx] = d[y][x] + 1;
                    prev[ny][nx] = y*C + x;
                    Q.push(pii(nx, ny));
                }
            }
        }
        int x = X[i], y = Y[i];
        vis[pii(x, y)].push_back(d[y][x]);           
        while (x != X[i-1] || y != Y[i-1]) {           
            int nx = x, ny = y;
            nx = prev[y][x] % C;
            ny = prev[y][x] / C;
            x = nx; y = ny;
            vis[pii(x, y)].push_back(d[y][x]);           
        }
    }
    int sum = 0;
    for (auto &v : vis) {
        int x = v.first.first;
        int y = v.first.second;
        vector<int> p = v.second;
        sum += cost[1][y][x] + cost[2][y][x];
        if (p.size() > 1) {
            for (int i = 1; i < (int)p.size(); i++) {
                sum += min(cost[2][y][x] + cost[1][y][x], (p[i] - p[i-1]) * cost[0][y][x]);
            }
        }
    }
    cout << sum << endl;
    return 0;
}