r.y, k = cur.k, s = cur.s; if (k == m && g[x][y] == 'T') ans = min(ans, cur.d); if (f[x][y][k][s] != -1) continue; f[x][y][k][s] = cur.d; for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; int st = g[nx][ny] - 'A'; if (st >= 0 && st < sn) { if ((1<
= '1' && g[nx][ny] < '1'+m) || g[nx][ny] == '.' || g[nx][ny] == 'K' || g[nx][ny] == 'T') q.push((Node){nx, ny, k, s, cur.d+1}); } } } return ans; } int main() { while (scanf("%d%d", &n, &m) != EOF && n+m) { memset(f, -1, sizeof(f)); memset(g, 0, sizeof(g)); sn = 0; for (int i = 1; i <= n; i++) { scanf("%s", g[i]+1); for (int j = 1; j <= n; j++) { if (g[i][j] == 'S') { g[i][j] = 'A' + sn; sn++; } if (g[i][j] == 'K') sx = i, sy = j; } } int ans = bfs(); if (ans == inf) printf("impossible\n"); else printf("%d\n", ans); } return 0; }
|