hdu 3681 Prison Break（dp || dfs）(二)
t", "r", stdout);
while(scanf("%d%d", &n, &m), n+m)
{
init();
build();
solve();
}
return 0;
}
[cpp]
//dfs爆搞 62ms。。。。
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define FF(i, a, b) for(int i=a; i
#define FD(i, a, b) for(int i=a; i>=b; i--)
#define REP(i, n) for(int i=0; i
#define CLR(a, b) memset(a, b, sizeof(a))
#define debug puts("**debug**")
#define LL long long
#define PB push_back
#define MP make_pair
using namespace std;
const int maxn = 20;
char g[maxn][maxn];
int n, m, S, tot, all, gank, goal, id[maxn], dist[maxn][maxn];
bool vis[maxn][maxn];
map mp, mp1;
map mp2;
struct Node
{
int u, steps;
Node(){}
Node(int a, int b) :u(a), steps(b){}
};
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
void bfs(int u)
{
queue q; q.push(Node(u, 0));
int xx = u/100, yy = u%100;
CLR(vis, 0); vis[xx][yy] = 1;
while(!q.empty())
{
Node T = q.front(); q.pop();
REP(i, 4)
{
int tx = T.u/100 + dx[i], ty = T.u%100 + dy[i];
if(tx<0 || tx>=n || ty<0 || ty>=m) continue;
if(vis[tx][ty] || g[tx][ty] == 'D') continue;
vis[tx][ty] = 1;
q.push(Node(tx*100+ty, T.steps+1));
if(g[tx][ty] != 'S')
{
int v = mp1[tx*100+ty];
dist[mp1[u]][v] = dist[v][mp1[u]] = T.steps+1;
}
}
}
return ;
}
void init()
{
tot = goal = 0;
CLR(dist, -1);
mp.clear(); mp1.clear(); mp2.clear();
}
void build()
{
REP(i, n)
{
scanf("%s", g[i]);
REP(j, m)
{
if(g[i][j] == 'F') id[tot] = 1, S = tot, mp2[tot] = g[i][j], mp[tot] = i*100+j, mp1[i*100+j] = tot++;
else if(g[i][j] == 'G') mp2[tot] = g[i][j], id[tot] = 2, mp[tot] = i*100+j, mp1[i*100+j] = tot++;
else if(g[i][j] == 'Y') goal |= 1<
}
}
all = (1<
REP(i, tot) bfs(mp[i]);
}
bool see[20];
bool dfs(int u, int res, int sta, int mid)
{
if((sta&goal) == goal) return true;
REP(v, tot) if(dist[u][v] > 0)
{
if(see[v] || res < dist[u][v]) continue;
if(mp2[v] == 'G')
{
see[v] = 1;
if(dfs(v, mid, sta|(1<
see[v] = 0;
}
else
{
see[v] = 1;
if(dfs(v, res-dist[u][v], sta|(1<
see[v] = 0;
}
}
return false;
}
bool ok(int mid)
{
CLR(see, 0);
see[S] = 1;
return dfs(S, mid, 1<
}
void solve()
{
REP(i, tot) if(i != S)
{
if(mp2[i] == 'Y' && dist[S][i] < 0)
{
puts("-1");
return ;
}
}
int L = 0, R = 2*n*m, M, ans = -1;
while(L <= R)
{
M = (L + R) >> 1;
if(ok(M)) ans = M, R = M - 1;
else L = M + 1;
}
printf("%d\n", ans);
}
int main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "r", stdout);
while(scanf("%d%d", &n, &m), n+m)
{
init();
build();
solve();
}
return 0;
}