#include using namespace std; #define forn(i,n) for(int i=0;i<(int)(n);i++) vector< vector > tablero(125, vector(125)); vector< vector< vector > > pasos(125, vector< vector >(125, vector(125, -1))); // para ver a los vecinos const int dx[4] = {0,0,1,-1}; const int dy[4] = {1,-1,0,0}; struct estado{ int x, y, f; estado(int nx, int ny, int nf): x(nx), y(ny), f(nf) {} }; bool estaAdentro(int x, int y, int M, int N){ return 0 <= x && x < M && 0 <= y && y < N; } int main(){ ifstream cin("tesoro.in"); ofstream cout("tesoro.out"); int M,N,F; cin >> M >> N >> F; int tX,tY; forn(i,M){ forn(j,N){ cin >> tablero[i][j]; if (tablero[i][j] == 'T'){ tX = i; tY = j; } } } int cfp = 0; int startF = F - (tablero[0][0] == 'W'); if (tablero[0][0] != 'P' && startF >= 0){ queue q; pasos[0][0][startF] = 0; q.push(estado(0, 0, startF)); while (!q.empty()){ estado actual = q.front(); q.pop(); int x = actual.x; int y = actual.y; int f = actual.f; // Ver vecinos forn(k,4){ int nx = x + dx[k]; int ny = y + dy[k]; if (estaAdentro(nx, ny, M, N)){ if (tablero[nx][ny] == 'W' && f > 0 && pasos[nx][ny][f-1] == -1){ pasos[nx][ny][f-1] = pasos[x][y][f]+1; q.push(estado(nx, ny, f-1)); } if ((tablero[nx][ny] == 'V' || tablero[nx][ny] == 'T') && pasos[nx][ny][f] == -1){ pasos[nx][ny][f] = pasos[x][y][f]+1; q.push(estado(nx, ny, f)); } } } } int res = 1000000000; for (int cf = 0; cf <= F; cf++){ if (pasos[tX][tY][cf] != -1 && pasos[tX][tY][cf] < res){ res = pasos[tX][tY][cf]; cfp = cf; } } } if (pasos[tX][tY][cfp] == -1){ cout << "imposible" << endl; }else{ cout << pasos[tX][tY][cfp] + 1 << endl; vector< pair > v; int x = tX, y = tY, f = cfp; while ((x != 0 || y != 0)){ v.push_back(make_pair(x, y)); forn(k,4){ int nx = x + dx[k]; int ny = y + dy[k]; if (estaAdentro(nx, ny, M, N)){ int costeFlecha = tablero[x][y] == 'W'; if (pasos[nx][ny][f+costeFlecha] + 1 == pasos[x][y][f]){ x = nx; y = ny; f = f + costeFlecha; break; } } } } v.push_back(make_pair(0,0)); forn(i, v.size()){ pair voy = v[v.size()-i-1]; // lo guardamos de atras para adelante, lo imprimimos en el orden del recorrido. cout<<"("<