[Codevs] 一塔湖图

http://codevs.cn/problem/1024/

floyd 走起

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define inf 0x7ffffff

#define gc getchar()

int x[], y[], n, m, t, k, x1, y1, x2, y2, a, b, f[][];

inline int read(){

    int x = ; char c = gc;

    while(c < '' || c > '') c = gc;

    while(c >= '' && c <= '') x = x *  + c - '', c = gc;

    return x;

}

int main()

{

    n = read(); m = read(); t = read(); k = read();

    for(int i = ; i <= n; i ++) x[i] = read();

    for(int i = ; i <= m; i ++) y[i] = read();

    for(int i = ; i <= n * m; i ++)

        for(int j = ; j <= n * m; j ++)

            if(i == j) f[i][j] = ; else f[i][j] = inf;

    for(int i = ; i <= n; i ++)

        for(int j = ; j <= m; j ++){

            if(i > ) {a = i - ; b = j; f[(j - ) * n + i][(b - ) * n + a] = x[i] - x[i - ];}

            if(j > ) {a = i; b = j - ; f[(j - ) * n + i][(b - ) * n + a] = y[j] - y[j - ];}

            if(i < n) {a = i + ; b = j; f[(j - ) * n + i][(b - ) * n + a] = x[i + ] - x[i];}

            if(j < m) {a = i; b = j + ; f[(j - ) * n + i][(b - ) * n + a] = y[j + ] - y[j];}

        }

    for(int i = ; i <= t; i ++){

        x1 = read(); y1 = read(); x2 = read(); y2 = read();

        f[(y1 - ) * n + x1][(y2 - ) * n + x2] = inf;

        f[(y2 - ) * n + x2][(y1 - ) * n + x1] = inf;

    }

    for(int i = ; i <= k; i ++) {

        x1 = read(); x2 = read(); y1 = read(); y2 = read();

        for(a = x1; a <= x2 - ; a ++)

            for(b = y1 + ; b <= y2 - ; b ++) {

                f[(b - ) * n + a][(b - ) * n + a + ] = inf;

                f[(b - ) * n + a + ][(b - ) * n + a] = inf;

            }

        for(b = y1; b <= y2 - ; b ++)

            for( a = x1 + ; a <= x2 -; a ++) {

                f[(b - ) * n + a][b * n + a] = inf;

                f[b * n + a][(b - ) * n + a] = inf;

            }

    }

    for(int k = ; k <= n * m; k ++)

        for(int i = ; i <= n * m; i ++)

            for(int j = ; j <= n * m; j ++)

                f[i][j] = min(f[i][k] + f[k][j], f[i][j]);

    x1 = read(); y1 = read(); x2 = read(); y2 = read();

    printf("%d", f[(y1 - ) * n + x1][(y2 - ) * n + x2]);

    return ;

}