hdu 3681 Prison Break(dp || dfs)

15Y...하지만 당시 hdu4766 21Y와는 거리가 멀어요...
처음에 이 문제를 받자마자 바로 bfs가 TLE를 한 발 했어요...그리고 그림의 빈 공간이 있어도 되고 없어도 되는 것을 발견하여 그림의 모든 F G Y를 추상화하여 그림을 만들고 bfs를 만들 수 있다.이 사고방식은 기본적으로 정해졌지요?
그래서 밤새 화를 냈어요...밤새 리제이 yy를 끌고 다녔더니 bfs가 모든 상태를 옮길 수 있을 것 같아...하지만 죽을 때까지...
그리고 인터넷에 접속한 사람들은 모두 dp로 상태 이동을 완성한 것을 발견했다.왜 bfs가 안 돼...(사실은 나의 bfs가 틀렸다는 것을 증명한다.)dp 해법을 만들었는데 AC가 됐어요...
이렇게 AC가 됐는데도 기분이 안 좋아서 bfs를 원망하고 있어요...만약 bfs가 해내지 못한다면 dfs는...그래서 또 dfs를 만들었어요...62ms..어이가 없어...
블로그 100번째 문제 이렇게 어렵게 왔는데...이 문제를 훑어보고, apm++...

// dp           390ms
#include<algorithm>
#include<iostream>
#include<cstring>
#include<fstream>
#include<sstream>
#include<cstdlib>
#include<vector>
#include<string>
#include<cstdio>
#include<bitset>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
#include<set>
#define FF(i, a, b) for(int i=a; i<b; i++)
#define FD(i, a, b) for(int i=a; i>=b; i--)
#define REP(i, n) for(int i=0; i<n; 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<int, int> mp, mp1;
map<int, char> 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<Node> 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<<tot, mp2[tot] = g[i][j], id[tot] = 3, mp[tot] = i*100+j, mp1[i*100+j] = tot++;
        }
    }
    all = (1<<tot);
    REP(i, tot) bfs(mp[i]);
}

int dp[15][1<<15];
bool ok(int mid)
{
    CLR(dp, -1);
    dp[S][1<<S] = mid;
    REP(s, all) REP(u, tot) if(dp[u][s] != -1 && (s & (1<<u)))
    {
        if((s & goal) == goal) return true;
        REP(v, tot) if(dist[u][v] > 0)
        {
            if(s & (1<<v)) continue;
            if(dp[u][s] < dist[u][v]) continue;
            int sta = s | (1<<v);
            if(dp[v][sta] == -1 || dp[v][sta] < dp[u][s] - dist[u][v])
                dp[v][sta] = dp[u][s] - dist[u][v];
            if(mp2[v] == 'G') dp[v][sta] = mid;
        }
    }
    return false;
}

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
", 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;
}

//dfs   62ms。。。。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<fstream>
#include<sstream>
#include<cstdlib>
#include<vector>
#include<string>
#include<cstdio>
#include<bitset>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
#include<set>
#define FF(i, a, b) for(int i=a; i<b; i++)
#define FD(i, a, b) for(int i=a; i>=b; i--)
#define REP(i, n) for(int i=0; i<n; 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<int, int> mp, mp1;
map<int, char> 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<Node> 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<<tot, mp2[tot] = g[i][j], id[tot] = 3, mp[tot] = i*100+j, mp1[i*100+j] = tot++;
        }
    }
    all = (1<<tot);
    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<<v), mid)) return true;
            see[v] = 0;
        }
        else
        {
            see[v] = 1;
            if(dfs(v, res-dist[u][v], sta|(1<<v), mid)) return true;
            see[v] = 0;
        }
    }
    return false;
}

bool ok(int mid)
{
    CLR(see, 0);
    see[S] = 1;
    return dfs(S, mid, 1<<S, mid);
}

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
", 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;
}