# AtCoder Regular Contest 019 C - 最後の森

,

## C - 最後の森

さっぱり分からなかったので答えを見ました。

### 実装

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cassert>
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
#define repeat(i,n) repeat_from(i,0,n)
template <class T>
using reversed_priority_queue = std::priority_queue<T, std::vector<T>, std::greater<T> >;
using namespace std;
struct state_t { int y, x; int k; int l; };
bool operator > (state_t const & a, state_t const & b) { return make_pair(a.l, a.k) > make_pair(b.l, b.k); }
const int dy[4] = { -1, 1, 0, 0 };
const int dx[4] = { 0, 0, 1, -1 };
vector<vector<vector<int> > > dijkstra(int r, int c, int k, vector<vector<char> > const & s, int y, int x) {
vector<vector<vector<int> > > result(r, vector<vector<int> >(c, vector<int>(k+1, -1)));
reversed_priority_queue<state_t> q;
q.push({ y, x, 0, 0 });
while (not q.empty()) {
state_t t = q.top(); q.pop();
if (result[t.y][t.x][t.k] != -1) continue;
result[t.y][t.x][t.k] = t.l;
repeat (i,4) {
int ny = t.y + dy[i];
int nx = t.x + dx[i];
if (not (0 <= ny and ny < r and 0 <= nx and nx < c)) continue;
if (s[ny][nx] == 'T') continue;
int nk = t.k + (s[ny][nx] == 'E' ? 1 : 0);
if (k < nk) continue;
if (result[ny][nx][nk] != -1) continue;
q.push({ ny, nx, nk, t.l+1 });
}
}
return result;
}
int main() {
int r, c, k; cin >> r >> c >> k;
vector<vector<char> > s(r, vector<char>(c));
int sy, sx, cy, cx, gy, gx;
repeat (y,r) repeat (x,c) {
cin >> s[y][x];
if (s[y][x] == 'S') { sy = y; sx = x; }
if (s[y][x] == 'C') { cy = y; cx = x; }
if (s[y][x] == 'G') { gy = y; gx = x; }
}
vector<vector<vector<int> > > dps = dijkstra(r, c, k, s, sy, sx);
vector<vector<vector<int> > > dpc = dijkstra(r, c, k, s, cy, cx);
vector<vector<vector<int> > > dpg = dijkstra(r, c, k, s, gy, gx);
int result = 1000000006;
repeat (y,r) repeat (x,c) {
int tk = k + (s[y][x] == 'E' ? 2 : 0);
repeat (ks,tk+1) {
if (dps[y][x][ks] == -1) continue;
if (s[y][x] == 'E') assert (ks != 0);
repeat (kc,tk-ks+1) {
if (dpc[y][x][kc] == -1) continue;
if (s[y][x] == 'E') assert (kc != 0);
repeat (kg,tk-ks-kc+1) {
if (dpg[y][x][kg] == -1) continue;
if (s[y][x] == 'E') assert (kg != 0);
result = min(result, dps[y][x][ks] + 2 * dpc[y][x][kc] + dpg[y][x][kg]);
}
}
}
}
if (result == 1000000006) result = -1;
cout << result << endl;
return 0;
}