#include #include #include #include using namespace std; static char mapa[2001][2001]; static char smer_prichodu[2001][2001]; static int skupina[2001][2001]; static int R, S; struct pozice { int r, s; pozice(void) { } pozice(int _r, int _s) : r(_r), s(_s) { } }; static const int smer[4][2] = {{0,1},{0,-1},{1,0},{-1,0}}; static const char smer_pismeno[4] = {'P', 'L', 'D', 'N'}; static char pismeno_na_opacny(char c) { switch (c) { case 'P' : return 1; case 'L': return 0; case 'D': return 3; case 'N': return 2; default: abort(); } } static bool pripustna(pozice const& p, int znic) { if (p.r < 0 || p.s < 0 || p.r > R - 2 || p.s > S - 2) return false; int nint = 0; nint += (mapa[p.r][p.s] == '#'); nint += (mapa[p.r + 1][p.s] == '#'); nint += (mapa[p.r][p.s + 1] == '#'); nint += (mapa[p.r + 1][p.s + 1] == '#'); return nint <= znic; } static void hledej_cesty_z(pozice const& z, int sk) { list fronta; fronta.push_back(z); skupina[z.r][z.s] = sk; smer_prichodu[z.r][z.s] = 0; while (!fronta.empty()) { pozice a = fronta.front(); fronta.pop_front(); for (int sm = 0; sm < 4; sm++) { pozice n(a.r + smer[sm][0], a.s + smer[sm][1]); if (!pripustna(n, 0) || skupina[n.r][n.s]) continue; skupina[n.r][n.s] = sk; smer_prichodu[n.r][n.s] = smer_pismeno[sm]; fronta.push_back(n); } } } static void vypis_cestu(pozice const &d) { vector cesta; vector::reverse_iterator ci; pozice a = d; char c; while ((c = smer_prichodu[a.r][a.s]) != 0) { cesta.push_back(c); int sm = pismeno_na_opacny(c); a.r += smer[sm][0]; a.s += smer[sm][1]; } for (ci = cesta.rbegin(); ci != cesta.rend(); ++ci) printf("%c", *ci); printf("\n"); } static bool dostupna(pozice const &k, int sk) { for (int sm = 0; sm < 4; sm++) { pozice pk(k.r + smer[sm][0], k.s + smer[sm][1]); if (pripustna(pk, 0) && skupina[pk.r][pk.s] == sk) return true; } return false; } static bool odstranitelna_pres(pozice const &k1, pozice const &k2, int zac_sk, int kon_sk) { if (!dostupna(k1, zac_sk) || !dostupna(k2, kon_sk)) return false; int dr = k1.r - k2.r; int ds = k1.s - k2.s; if (abs(dr) + abs(ds) < 2) return true; int minr, maxr, mins, maxs; minr = min(k1.r, k2.r); maxr = max(k1.r + 1, k2.r + 1); mins = min(k1.s, k2.s); maxs = max(k1.s + 1, k2.s + 1); int nint = 0; for (int r = minr; r <= maxr; r++) for (int s = mins; s <= maxs; s++) if (mapa[r][s] == '#') nint++; if (nint < 3) return true; for (int sm = 0; sm < 4; sm++) { pozice pk1(k1.r + smer[sm][0], k1.s + smer[sm][1]); if (!pripustna(pk1, 0)) continue; if (dostupna(k2, skupina[pk1.r][pk1.s])) return true; } return false; } static bool odstranitelna(pozice const &p, int zac_sk, int kon_sk) { for (int r1 = -1; r1 <= 0; r1++) for (int s1 = -1; s1 <= 0; s1++) { pozice k1(p.r + r1, p.s + s1); if (!pripustna(k1, 1)) continue; for (int r2 = -1; r2 <= 0; r2++) for (int s2 = -1; s2 <= 0; s2++) { pozice k2(p.r + r2, p.s + s2); if (pripustna(k2, 1) && odstranitelna_pres(k1, k2, zac_sk, kon_sk)) return true; } } return false; } int main(void) { pozice zacatek, konec; bool zacatek_nastaven = false; bool konec_nastaven = false; scanf("%d%d", &R, &S); for (int r = 0; r < R; r++) { scanf("%s", mapa[r]); for (int s = 0; s < S; s++) { if (mapa[r][s] == '#') continue; if (mapa[r][s] == 'K' && !zacatek_nastaven) { zacatek.r = r; zacatek.s = s; zacatek_nastaven = true; } if (mapa[r][s] == 'T' && !konec_nastaven) { konec.r = r; konec.s = s; konec_nastaven = true; } mapa[r][s] = '.'; } } int pocet_skupin = 1; hledej_cesty_z(zacatek, 1); if (skupina[konec.r][konec.s] == 1) { vypis_cestu(konec); return 0; } for (int r = 0; r < R - 1; r++) for (int s = 0; s < S - 1; s++) { pozice a(r, s); if (!skupina[r][s] && pripustna(a, 0)) hledej_cesty_z(a, ++pocet_skupin); } int kon_sk = skupina[konec.r][konec.s]; for (int r = 0; r < R; r++) for (int s = 0; s < S; s++) if (mapa[r][s] == '#') { if (odstranitelna(pozice(r, s), 1, kon_sk)) { mapa[r][s] = '.'; for (int r1 = 0; r1 < R; r1++) for (int s1 = 0; s1 < S; s1++) skupina[r1][s1] = 0; hledej_cesty_z(zacatek, 1); vypis_cestu(konec); return 0; } } printf("nelze\n"); return 0; }