#include #include #include using namespace std; const int L = 200; const int T = 10; const int dx[4] = {1, 0, -1, 0}; const int dy[4] = {0, 1, 0, -1}; char map[L][L + 1]; bool flag[L][L][T]; struct Pos { int x; int y; int t; int r; Pos(int x = 0, int y = 0, int t = 0, int r = 0) : x(x), y(y), t(t), r(r) {} bool operator==(const Pos &that) const { return this->x == that.x && this->y == that.y; } }; int m, n; int is_expandable(int x, int y, int t) { if (x < 0 || m <= x || y < 0 || n <= y) return false; if (map[x][y] == '#') return t != 0 && !flag[x][y][t - 1]; if (flag[x][y][t]) return false; return true; } int main() { int t; scanf("%d %d %d", &m, &n, &t); Pos naruto, sasuke; for (int i = 0; i < m; i++) { scanf("%s", map[i]); for (int j = 0; j < n; j++) { if (map[i][j] == '@') { naruto.x = i; naruto.y = j; naruto.t = t; } else if (map[i][j] == '+') { sasuke.x = i; sasuke.y = j; sasuke.r = -1; } } } queue q; q.push(naruto); memset(flag, 0, sizeof(flag)); flag[naruto.x][naruto.y][naruto.t] = true; while (!q.empty()) { Pos &cur = q.front(); q.pop(); if (cur == sasuke) { sasuke.r = cur.r; break; } for (int i = 0; i < 4; i++) { int nx = cur.x + dx[i]; int ny = cur.y + dy[i]; if (!is_expandable(nx, ny, cur.t)) continue; if (map[nx][ny] == '#') { q.emplace(nx, ny, cur.t - 1, cur.r + 1); flag[nx][ny][cur.t - 1] = true; } else { q.emplace(nx, ny, cur.t, cur.r + 1); flag[nx][ny][cur.t] = true; } } } printf("%d\n", sasuke.r); return 0; }