2012-0013

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

还是让我这个苦逼的作者写吧T T
简单来说就是构图 + 最短路，直接贴代码：
复杂度O(|E|log|V|)

{{{
#include <cassert>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;


const int maxN = 110;
const int len = (maxN * maxN) << 2;
const int inf = 0x7FFFFFFF;
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};

typedef pair<int, int> Rec;

struct point
{
    int v, w, next;
}edge[len << 2];

int n, m, s, g[4][maxN][maxN], vect[len], d[len], f[len];            //4层图， vect和edge大概就是一个前向星的东西
int r, tx, ty, st, ans_D, ans_F;
int tol, cnt, st_x, st_y, en_x, en_y;
bool vis[len];
char c;


int get(char c)
{
    if (c == 'E') return 0;
    if (c == 'S') return 1;
    if (c == 'W') return 2;
    if (c == 'N') return 3;
}

int mark(int t, int x, int y)                   //求时刻t坐标(x, y)的编号
{
    return t * n * m + (x - 1) * m + y;
}

void add(int u, int v, int w)                   //添加边
{    
    //printf("%d %d %d \n", u, v, w);
    cnt++;
    edge[cnt].v = v;
    edge[cnt].w = w;
    edge[cnt].next = vect[u];
    vect[u] = cnt;
}

void build()                                                        // 构图
{
    st = mark(0, st_x, st_y);
    tol = n * m * 4;
    cnt = 0;
    memset(vect, 0, sizeof(vect));
    for (int t = 0; t < 4; t++){
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= m; j++){
                if (g[t][i][j] == -1) continue;
                for (int k = 0; k < 4; k++){
                    tx = i + dx[k];
                    ty = j + dy[k];
                    if (tx < 1 || ty < 1 || tx > n || ty > m) continue;
                    if (g[(t + 1) % 4][tx][ty] == -1) continue;
                    add(mark(t, i, j), mark((t + 1) % 4, tx, ty), g[(t + 1) % 4][tx][ty]); 
                }
            }
        }
    }
}   

void solve()                                          //Dijkstra +　priority_queue；数组d[u]表示到u的最少的守护者,f[u]表示最少的时间.
{
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= tol; i++){
        d[i] = inf;
        f[i] = inf;
    }
    d[st] = g[0][st_x][st_y];
    f[st] = 0;

    priority_queue< pair<int, Rec>, vector< pair<int, Rec> >, greater<pair<int, Rec> > > heap;
    heap.push( make_pair(d[st], make_pair(f[st], st)));
    while(!heap.empty()){
        int u = heap.top().second.second;
        heap.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (int tt = vect[u]; tt; tt = edge[tt].next){
            int v = edge[tt].v;
            if (!vis[v]){
                if (d[v] > d[u] + edge[tt].w || d[v] == d[u] + edge[tt].w && f[v] > f[u] + 1){
                    d[v] = d[u] + edge[tt].w;
                    f[v] = f[u] + 1;
                    heap.push( make_pair(d[v], make_pair(f[v], v) ) );
                }    
            }
        }
    }
}

int main()
{
    while(scanf("%d%d%d", &n, &m, &s) != EOF){

        getchar();
        assert(2 <= n && n <= 100); 
        assert(2 <= m && m <= 100);
        assert(1 <= s && s <= n*m);
        memset(g, 0, sizeof(g));
        for (int i = 1; i <= n; i++){                                //g记录地图的情况, -1表示不能走进,0表示空地,其他正数表示守护者看到这个格子的数目.
            for (int j = 1; j <= m; j++){
                c = getchar();
                if (c == '*')
                g[0][i][j] = g[1][i][j] = g[2][i][j] = g[3][i][j] = -1;
            }
            getchar();
        }
        int x, y;
        for (int i = 1; i <= s; i++){
            scanf("%d%d%d%c%c", &x, &y, &r, &c, &c);
            assert(1 <= x && x <= n);
            assert(1 <= y && y <= m);
            assert(1 <= r && r <= 100);
            assert(c == 'E' || c == 'S' || c == 'W' || c == 'N');
            g[0][x][y] = g[1][x][y] = g[2][x][y] = g[3][x][y] = -1;
            for (int k = 0; k < 4; k++){
                for (int L = 1; L <= r; L++){
                    int t = (get(c) + k) % 4;
                    tx = x + dx[t] * L;
                    ty = y + dy[t] * L;
                    if (tx < 1 || ty < 1 || tx > n || ty > m) break;
                    if (g[k][tx][ty] != -1) g[k][tx][ty]++;    //这里的k写成了t，悲剧.
                }
            }

        }
        scanf("%d%d%d%d", &st_x, &st_y, &en_x, &en_y);

        build();
        solve();
        ans_D = ans_F = inf;
        for (int t = 0; t < 4; t++){
            int tp = mark(t, en_x, en_y);
            if (ans_D > d[tp] || ans_D == d[tp] && ans_F > f[tp]){
                ans_D = d[tp];
                ans_F = f[tp];
            }
        }
        if (ans_D == inf) 
            printf("-1\n");
        else
            printf("%d %d\n", ans_D, ans_F);               
    }   
    return 0;
}
}}}


=====================================

思考了一下之后觉得bfs貌似可以做><

还是让我这个苦逼的作者写吧T T

简单来说就是构图 + 最短路，直接贴代码：

复杂度O(|E|log|V|)

#include <cassert>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
const int maxN = 110;
const int len = (maxN * maxN) << 2;
const int inf = 0x7FFFFFFF;
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
typedef pair<int, int> Rec;
struct point
{
    int v, w, next;
}edge[len << 2];
int n, m, s, g[4][maxN][maxN], vect[len], d[len], f[len];            //4层图， vect和edge大概就是一个前向星的东西
int r, tx, ty, st, ans_D, ans_F;
int tol, cnt, st_x, st_y, en_x, en_y;
bool vis[len];
char c;
int get(char c)
{
    if (c == 'E') return 0;
    if (c == 'S') return 1;
    if (c == 'W') return 2;
    if (c == 'N') return 3;
}
int mark(int t, int x, int y)                   //求时刻t坐标(x, y)的编号
{
    return t * n * m + (x - 1) * m + y;
}
void add(int u, int v, int w)                   //添加边
{    
    //printf("%d %d %d \n", u, v, w);
    cnt++;
    edge[cnt].v = v;
    edge[cnt].w = w;
    edge[cnt].next = vect[u];
    vect[u] = cnt;
}
void build()                                                        // 构图
{
    st = mark(0, st_x, st_y);
    tol = n * m * 4;
    cnt = 0;
    memset(vect, 0, sizeof(vect));
    for (int t = 0; t < 4; t++){
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= m; j++){
                if (g[t][i][j] == -1) continue;
                for (int k = 0; k < 4; k++){
                    tx = i + dx[k];
                    ty = j + dy[k];
                    if (tx < 1 || ty < 1 || tx > n || ty > m) continue;
                    if (g[(t + 1) % 4][tx][ty] == -1) continue;
                    add(mark(t, i, j), mark((t + 1) % 4, tx, ty), g[(t + 1) % 4][tx][ty]); 
                }
            }
        }
    }
}   
void solve()                                          //Dijkstra +　priority_queue；数组d[u]表示到u的最少的守护者,f[u]表示最少的时间.
{
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= tol; i++){
        d[i] = inf;
        f[i] = inf;
    }
    d[st] = g[0][st_x][st_y];
    f[st] = 0;
    priority_queue< pair<int, Rec>, vector< pair<int, Rec> >, greater<pair<int, Rec> > > heap;
    heap.push( make_pair(d[st], make_pair(f[st], st)));
    while(!heap.empty()){
        int u = heap.top().second.second;
        heap.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (int tt = vect[u]; tt; tt = edge[tt].next){
            int v = edge[tt].v;
            if (!vis[v]){
                if (d[v] > d[u] + edge[tt].w || d[v] == d[u] + edge[tt].w && f[v] > f[u] + 1){
                    d[v] = d[u] + edge[tt].w;
                    f[v] = f[u] + 1;
                    heap.push( make_pair(d[v], make_pair(f[v], v) ) );
                }    
            }
        }
    }
}
int main()
{
    while(scanf("%d%d%d", &n, &m, &s) != EOF){
        getchar();
        assert(2 <= n && n <= 100); 
        assert(2 <= m && m <= 100);
        assert(1 <= s && s <= n*m);
        memset(g, 0, sizeof(g));
        for (int i = 1; i <= n; i++){                                //g记录地图的情况, -1表示不能走进,0表示空地,其他正数表示守护者看到这个格子的数目.
            for (int j = 1; j <= m; j++){
                c = getchar();
                if (c == '*')
                g[0][i][j] = g[1][i][j] = g[2][i][j] = g[3][i][j] = -1;
            }
            getchar();
        }
        int x, y;
        for (int i = 1; i <= s; i++){
            scanf("%d%d%d%c%c", &x, &y, &r, &c, &c);
            assert(1 <= x && x <= n);
            assert(1 <= y && y <= m);
            assert(1 <= r && r <= 100);
            assert(c == 'E' || c == 'S' || c == 'W' || c == 'N');
            g[0][x][y] = g[1][x][y] = g[2][x][y] = g[3][x][y] = -1;
            for (int k = 0; k < 4; k++){
                for (int L = 1; L <= r; L++){
                    int t = (get(c) + k) % 4;
                    tx = x + dx[t] * L;
                    ty = y + dy[t] * L;
                    if (tx < 1 || ty < 1 || tx > n || ty > m) break;
                    if (g[k][tx][ty] != -1) g[k][tx][ty]++;    //这里的k写成了t，悲剧.
                }
            }
        }
        scanf("%d%d%d%d", &st_x, &st_y, &en_x, &en_y);
        build();
        solve();
        ans_D = ans_F = inf;
        for (int t = 0; t < 4; t++){
            int tp = mark(t, en_x, en_y);
            if (ans_D > d[tp] || ans_D == d[tp] && ans_F > f[tp]){
                ans_D = d[tp];
                ans_F = f[tp];
            }
        }
        if (ans_D == inf) 
            printf("-1\n");
        else
            printf("%d %d\n", ans_D, ans_F);               
    }   
    return 0;
}

=====================================

思考了一下之后觉得bfs貌似可以做><