poj2312

#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <queue> using namespace std; #define maxn 305 struct Point { int x, y, w; }s, t; int n, m; char map[maxn][maxn]; bool vis[maxn][maxn]; int dir[4][2] = { { 1,0},{-1,0},{ 0,1},{ 0,-1}}; bool operator < (const Point &a, const Point &b) { return a.w > b.w; } void input() { for (int i = 0; i < n; i++) scanf("%s", map[i]); } void work() { for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { if (map[i][j] == 'Y') { s.x = i; s.y = j; s.w = 0; map[i][j] = 'E'; } if (map[i][j] == 'T') { t.x = i; t.y = j; map[i][j] = 'E'; } } } bool ok(Point a, int &step) { if (a.x < 0 || a.y < 0 || a.x >= n || a.y >= m) return false; if (vis[a.x][a.y]) return false; if (map[a.x][a.y] == 'S' ||map[a.x][a.y] == 'R') return false; if (map[a.x][a.y] == 'E') { step = 1; return true; } step = 2; return true; } int bfs() { priority_queue <Point> pq; memset(vis, 0, sizeof(vis)); pq.push(s); vis[s.x][s.y] = true; while (!pq.empty()) { Point u = pq.top(); pq.pop(); if (u.x == t.x && u.y == t.y) return u.w; Point v; for (int i = 0; i < 4; i++) { v.x = u.x + dir[i][0]; v.y = u.y + dir[i][1]; int step; if (ok(v, step)) { v.w = u.w + step; pq.push(v); vis[v.x][v.y] = true; } } } return -1; } int main() { //freopen("t.txt", "r", stdin); while (scanf("%d%d", &n, &m), n | m) { input(); work(); printf("%d\n", bfs()); } return 0; }