题目：http://codeforces.com/problemset/problem/366/E

事实上就是找 n * m 矩阵中数字 x 和 数字 y 的最远距离。

方法參照武森的论文《浅谈信息学中的“0”和“1”》

先约定符号：xi,xj  (i,j)是x的下标，当然。矩阵中的值是能够反复的

上面是武森的论文原文。加上我之前的符号约定，我在做点解释：

事实上那个max={四种可能}  更好的写法是：

|xi-yi|+|xj-yj|=max((1),(2),(3),(4))

(1)（xi+xj）-(yi+yj)   就是3-3  最大就是max3-min3

(2)(xi-xj)-(yi-yj)      2-2  最大就是max2-min2

(3)(-xi+xj)-(-yi+yj)  1-1  最大就是max1-min1

(4)(-xi-xj)-(-yi-yj)    0-0  最大就是max0-min0

那么维护数组num[v][4][2]    num[v][4][0]   就是0 1 2 3 情况下的最小值。num[v][4][1]   就是0 1 2 3 情况下的最大值。由于v能够出如今矩阵的多个位置就是说矩阵能够有反复值。所以维护的[0] [1]可能不是一个坐标处的，可是也是能够的

这么解释应该都能理解，然后假设是多维。只是是维护num[v][8][2]----剩下的。你懂得~~~

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <string>

#include <iostream>

#include <iomanip>

#include <cmath>

#include <map>

#include <set>

#include <queue>

using namespace std;

#define ls(rt) rt*2

#define rs(rt) rt*2+1

#define ll long long

#define ull unsigned long long

#define rep(i,s,e) for(int i=s;i<e;i++)

#define repe(i,s,e) for(int i=s;i<=e;i++)

#define CL(a,b) memset(a,b,sizeof(a))

#define IN(s) freopen(s,"r",stdin)

#define OUT(s) freopen(s,"w",stdout)

const ll ll_INF = ((ull)(-1))>>1;

const int INF = 100000000;

const double EPS = 1e-8;

int ABS(int x)

{

    return x>=0?x:(-x);

}

int a[10][4][2];

int n,m,k,s;

int main()

{

    //IN("in.txt");

    int x,y;

    while(~scanf("%d%d%d%d",&n,&m,&k,&s))

    {

        for(int i=0;i<10;i++)

            for(int j=0;j<4;j++)

            {

                a[i][j][0]=INF;//0  min

                a[i][j][1]=-INF;//1 max

            }

        //printf("cap\n");

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

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

            {

                scanf("%d",&x);

                a[x][0][0]=min(a[x][0][0],-i-j);

                a[x][0][1]=max(a[x][0][1],-i-j);

                a[x][1][0]=min(a[x][1][0],-i+j);

                a[x][1][1]=max(a[x][1][1],-i+j);

                a[x][2][0]=min(a[x][2][0],i-j);

                a[x][2][1]=max(a[x][2][1],i-j);

                a[x][3][0]=min(a[x][3][0],i+j);

                a[x][3][1]=max(a[x][3][1],i+j);

            }

        int ans=0;

        scanf("%d",&x);

        for(int i=1;i<s;i++)

        {

            scanf("%d",&y);

            for(int j=0;j<4;j++)

            {

                 ans=max(ans,ABS(a[x][j][1]-a[y][j][0]));

                 ans=max(ans,ABS(a[x][j][0]-a[y][j][1]));

            }

            x=y;

        }

        printf("%d\n",ans);

    }

    return 0;

}

还看到还有一种做法也是不错的：http://vawait.com/codeforces-366e/

事实上道理一样

(1)（xi+xj）-(yi+yj)=xi+xj+(-yi-yj)   就是3+0  最大就是max3+max0

(2)(xi-xj)+(-yi+yj)      2+1  最大就是max2+max1

(3)(-xi+xj)+(yi-yj)  1+2  最大就是max1+max2

(4)(-xi-xj)+(yi+yj)    0+3  最大就是max0+max3

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cmath>

#include<algorithm>

#include<string>

#include<map>

#include<set>

#include<vector>

#include<queue>

#include<stack>

using namespace std;

#define rep(i, a, b) for (int i = (a); i <= (b); ++i)

#define red(i, a, b) for (int i = (a); i >= (b); --i)

#define clr( x , y ) memset(x,y,sizeof(x))

#define sqr(x) ((x) * (x))

typedef long long lint;

int n,m,k,s,x,y,a[10][5];

void init()

{

    scanf("%d%d%d%d",&n,&m,&k,&s);

    clr(a,243);

    rep(i,1,n)

        rep(j,1,m) {

            scanf("%d",&x);

            a[x][0] = max( a[x][0] , -i - j );

            a[x][1] = max( a[x][1] , -i + j );

            a[x][2] = max( a[x][2] , i - j );

            a[x][3] = max( a[x][3] , i + j );

        }

}

void work()

{

    int ans = -100000000;

    scanf("%d",&x);

    rep(i,2,s) {

        scanf("%d",&y);

        rep(j,0,3) ans = max( ans , a[x][j] + a[y][3-j] );

        x = y;

    }

    cout<<ans;

}

int main()

{

    init();

    work();

    return 0;

}