ZOJ3103 Cliff Climbing 最短路

题意：从若干个S点出发到达T点，稍有不同的是，要区分该点落脚有左脚和右脚两种情况。

解法：从题目中给定的S出发，左脚和右脚都可以踏上去，全部入队列后再spfa即可。做了这题发现使用spfa来处理多源点时连超级源点都不用建立了。

代码如下：

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
using namespace std;

const int INF = 0x3f3f3f3f;
int N, M, dis[2][65][35];
char G[65][35], vis[2][65][35];

struct Point {
    int x, y;
    Point(int x_, int y_) {x = x_, y = y_;}
    Point(){}
};

vector<Point>S;

bool judge(int lx, int ly, int rx, int ry) {
    if (lx < 1 || rx < 1 || lx > N || rx > N || ly < 1 || ry < 1 || ly > M || ry > M)
        return false;
    if (ly < ry && abs(lx-rx) + abs(ly-ry) <= 3)
        return true;
    return false;
}

int ldir[9][2] = {{0,-1},{0,-2},{0,-3},{1,-1},{1,-2},{2,-1},{-1,-1},{-1,-2},{-2,-1}};
int rdir[9][2] = {{0,1},{0,2},{0,3},{1,1},{1,2},{2,1},{-1,1},{-1,2},{-2,1}};

void spfa() {
    Point v;
    memset(vis, 0, sizeof (vis));
    memset(dis, 0x3f, sizeof (dis));
    queue<Point>q;
    for (int i = 0; i != S.size(); ++i) {
        q.push(S[i]);
        dis[0][S[i].x][S[i].y] = 0;
        dis[1][S[i].x][S[i].y] = 0;
        vis[0][S[i].x][S[i].y] = 1;
        vis[1][S[i].x][S[i].y] = 1;
    }
    while (!q.empty()) {
        v = q.front();
        q.pop();
            // 首先是踏左脚
        if (vis[1][v.x][v.y]) { // 如果右脚在队列之中
            vis[1][v.x][v.y] = 0; 
            for (int k = 0; k < 9; ++k) {
                int i = v.x + ldir[k][0], j = v.y + ldir[k][1];
                if (judge(i, j, v.x, v.y) && G[i][j] != 'X') {
                    int ti = (G[i][j] == 'S' || G[i][j] == 'T') ? 0 : G[i][j] - '0';
                    if (dis[0][i][j] > dis[1][v.x][v.y] + ti) {
                        dis[0][i][j] = dis[1][v.x][v.y] + ti;
                        if (!vis[0][i][j]) {
                            q.push(Point(i, j));
                            vis[0][i][j] = 1;
                        }
                    }
                }
            }
        }
        // 如果是踏右脚
        if (vis[0][v.x][v.y]) {
            vis[0][v.x][v.y] = 0;
            for (int k = 0; k < 9; ++k) {
                int i = v.x + rdir[k][0], j = v.y + rdir[k][1];
                if (judge(v.x, v.y, i, j) && G[i][j] != 'X') {
                    int ti = (G[i][j] == 'S' || G[i][j] == 'T') ? 0 : G[i][j] - '0';
                    if (dis[1][i][j] > dis[0][v.x][v.y] + ti) {
                        dis[1][i][j] = dis[0][v.x][v.y] + ti;
                        if (!vis[1][i][j]) {
                            q.push(Point(i, j));
                            vis[1][i][j] = 1;
                        }
                    }
                }
            }
        }
    }
}


int main() {
    while (cin >> M >> N, N|M) {
        getchar();
        S.clear();
        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j <= M; ++j) {
                scanf("%c%*c", &G[i][j]);
                if (G[i][j] == 'S') {
                    S.push_back(Point(i, j));    
                }
            }
        }
        spfa();
        int Min = INF;
        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j <= M; ++j) {
                if (G[i][j] == 'T') {
                    Min = min(Min, min(dis[0][i][j], dis[1][i][j]));
                }
            }
        }
        if (Min != INF) {
            printf("%d\n", Min);
        } else printf("-1\n");
    }
    return 0;
}