ACM – Uva10047 – 图论

点击量:31

隐式图搜索,多个状态然后减枝。。没看懂李大大所说可以承受是个啥意思。。

做起来实在太累了。。减枝的部分看了别人的代码,发现着实麻烦,不如用优先队列来的痛快=- =还有用优先队列做的= =

主要是$vis[x][y][p][c]$这组状态比较难搞,但是给了优先级(时间短的先出队),事情就好办了。

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long int
#define MEM(a) memset(a, 0, sizeof(a))
#define MEMM(a) memset(a, -1, sizeof(a))
#define DEB(x, n) cout << (x) << " " << (n) << endl
#define FOR(i, s, e) for(int (i) = (s); (i) < (e); (i)++)
#define CR printf("\n")
const double PI = acos(-1.0);
const int maxn = 30;
char g[maxn][maxn];
// c, 0, 1, 2, 3, 4
// blue,w,g,black,r;
struct Node {
    int x, y, c, p, t;
    Node(int x, int y, int c, int p, int t):x(x), y(y), c(c), p(p), t(t){}
    Node(){}
    bool operator < (const Node b) const {
        return t > b.t;
    }
};
Node s, e;
int n, m;
inline int judge(int x, int y)
{
    return x >= 0 && x < m && y >= 0 && y < n;
}
bool vis[maxn][maxn][4][5];
void test() {
    for(int i = 0; i<m ;i++) {
        for(int j = 0; j <n; j++ ) {
            printf("%2c", g[i][j]);
        }
        cout << endl;
    }
}
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int bfs()
{
    priority_queue <Node> q;
    Node t, next;
    int ans = INF;
    q.push(s);
    while(!q.empty())
    {
        t = q.top(), q.pop();
        vis[t.x][t.y][t.p][t.c] = 1;
        if(t.x == e.x && t.y == e.y && t.c == e.c) return t.t;
        for(int i = 0; i < 4; i++)
        {
            next.x = t.x + dx[i];
            next.y = t.y + dy[i];
            next.c = (t.c+1)%5;
            next.p = i;
            if(next.p == t.p)
                next.t = t.t+1;
            else if(abs(next.p-t.p) == 2)
                next.t = t.t+3;
            else
                next.t = t.t+2;
            if(g[next.x][next.y] != '#' && !vis[next.x][next.y][next.p][next.c]
                    && judge(next.x, next.y))
                q.push(next);
        }
    }
    return ans;
}
int main()
{
#ifdef DEBUG
    freopen("input", "r", stdin);       //从input文件中读入
    // freopen("output", "w", stdout);     //输出到output文件
#endif
    int kase = 1;
    while(scanf("%d%d", &m, &n) != EOF)
    {
        MEM(vis);
        if(n == 0 && m == 0) break;
        for(int i = 0; i < m; i++)
            scanf("%s", g[i]);
        // read 
        for(int i = 0; i < m ;i ++) {
            for(int j = 0;j < n; j++) {
                if(g[i][j] == 'S') s = Node(i, j, 2, 0, 0);
                else if(g[i][j] == 'T') e = Node(i, j, 2, 0, 0);
            }
        }
        int ans = bfs();
        if(kase != 1) CR;
        printf("Case #%d\n", kase++);
        if(ans == INF) puts("destination not reachable");
        else printf("minimum time = %d sec\n", ans);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注