cf E. Dima and Magic Guitar

http://codeforces.com/contest/366/problem/E

|x1-x2|+|y1-y2|有四种情况

1.-(x1-x2)+(y1-y2);

2.(x1-x2)-(y1-y2);

3.-(x1-x2)-(y1-y2);

4.(x1-x2)+(y1-y2);

可以先把没一个数的坐标分为上面的四种情况存起来，然后在S序列相邻的两个数的曼哈顿距离最大就是两个数中的一个数的四种情况最大值减去另一个数的最小值。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 #include <vector>
 5 #include <algorithm>
 6 #define maxn 20000
 7 using namespace std;
 8 const int inf=1<<29;
 9 
10 int n,m,k,s;
11 int a[maxn];
12 int g[20][4][2];
13 
14 int main()
15 {
16     while(scanf("%d%d%d%d",&n,&m,&k,&s)!=EOF)
17     {
18         for(int i=1; i<=k; i++)
19         {
20             for(int j=0; j<4; j++)
21             {
22                 g[i][j][0]=-inf;
23                 g[i][j][1]=inf;
24             }
25         }
26         for(int i=1; i<=n; i++)
27         {
28             for(int j=1; j<=m; j++)
29             {
30                 int c;
31                 scanf("%d",&c);
32                 g[c][0][0]=max(g[c][0][0],i+j);
33                 g[c][0][1]=min(g[c][0][1],i+j);
34                 g[c][1][0]=max(g[c][1][0],-i+j);
35                 g[c][1][1]=min(g[c][1][1],-i+j);
36                 g[c][2][0]=max(g[c][2][0],-i-j);
37                 g[c][2][1]=min(g[c][2][1],-i-j);
38                 g[c][3][0]=max(g[c][3][0],i-j);
39                 g[c][3][1]=min(g[c][3][1],i-j);
40             }
41         }
42         int x;
43         scanf("%d",&x);
44         int last=x;
45         int max1=0;
46         for(int i=2; i<=s; i++)
47         {
48             scanf("%d",&x);
49             for(int j=0; j<4; j++)
50             {
51                 max1=max(max1,abs(g[x][j][0]-g[last][j][1]));
52                 max1=max(max1,abs(g[x][j][1]-g[last][j][0]));
53             }
54             last=x;
55         }
56         printf("%d
",max1);
57     }
58     return 0;
59 }

View Code