CodeForces 366 E. Dima and Magic Guitar

E. Dima and Magic Guitar

time limit per test

3 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Dima loves Inna very much. He decided to write a song for her. Dima has a magic guitar withnstrings andmfrets. Dima makes the guitar produce sounds like that: to play a note, he needs to hold one of the strings on one of the frets and then pull the string. When Dima pulls thei-th string holding it on thej-th fret the guitar produces a note, let's denote it asaij. We know that Dima's guitar can producekdistinct notes. It is possible that some notes can be produced in multiple ways. In other words, it is possible thataij = apqat(i, j) ≠ (p, q).

Dima has already written a song — a sequence ofsnotes. In order to play the song, you need to consecutively produce the notes from the song on the guitar. You can produce each note in any available way. Dima understood that there are many ways to play a song and he wants to play it so as to make the song look as complicated as possible (try to act like Cobein).

We'll represent a way to play a song as a sequence of pairs(xi, yi)(1 ≤ i ≤ s), such that thexi-th string on theyi-th fret produces thei-th note from the song. The complexity of moving between pairs(x1, y1)and(x2, y2)equals+. The complexity of a way to play a song is the maximum of complexities of moving between adjacent pairs.

Help Dima determine the maximum complexity of the way to play his song! The guy's gotta look cool!

Input

The first line of the input contains four integersn,m,kands(1 ≤ n, m ≤ 2000, 1 ≤ k ≤ 9, 2 ≤ s ≤ 105).

Then follownlines, each containingmintegersaij(1 ≤ aij ≤ k). The number in thei-th row and thej-th column (aij) means a note that the guitar produces on thei-th string and thej-th fret.

The last line of the input containssintegersqi(1 ≤ qi ≤ k)— the sequence of notes of the song.

Output

In a single line print a single number — the maximum possible complexity of the song.

Sample test(s)

input

4 6 5 7
3 1 2 2 3 1
3 2 2 2 5 5
4 2 2 2 5 3
3 2 2 1 4 3
2 3 1 4 1 5 1

output

8

input

4 4 9 5
4 7 9 5
1 2 1 7
8 3 4 9
5 7 7 2
7 1 9 2 5

output

4

寻找串S中的每个数字在给定的矩阵中的位置，使S中相邻的两个数的曼哈顿距离最大，并输出相邻的数的最大曼哈顿距离。。。。（题目真难懂）

| x1 - x2 | - | y1 - y2 |=以下4种情况下的最大值

one:

x1-x2+y1-y2 ---> (x1+y1) - (x2+y2)

two:

-(x1-x2) + (y1-y2) ---> (x2-y2) - (x1-y1)

three:

(x1-x2) - (y1-y2) ---> (x1-y1) - (x2-y2)

four:
-( x1-x2 ) - (y1-y2) ---> (x2+y2) - (x1+y1)

曼哈顿距离可以用两个点的纵横坐标表示出来，对每个数字可以维护使减号前的值最大，减号后的值最小

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdio>

using namespace std;

int n,m,k,s;
int f[10][2],b[10][2];

int max5(int a,int b,int c,int d,int e)
{
    return max(a,max(max(b,c),max(d,e)));
}

int main()
{
    memset(f,192,sizeof(f));
    memset(b,63,sizeof(b));
    scanf("%d%d%d%d",&n,&m,&k,&s);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int a;
            scanf("%d",&a);
            f[a][0]=max(f[a][0],i+j); f[a][1]=max(f[a][1],i-j);
            b[a][0]=min(b[a][0],i+j); b[a][1]=min(b[a][1],i-j);
        }
    }
    int p,q,ans=0;
    for(int i=0;i<s;i++,p=q)
    {
        scanf("%d",&q);
        if(i)
        {
            int t1=f[p][0]-b[q][0];
            int t2=f[q][1]-b[p][1];
            int t3=f[p][1]-b[q][1];
            int t4=f[q][0]-b[p][0];
            ans=max5(ans,t1,t2,t3,t4);
        }
    }
    printf("%d\n",ans);
    return 0;
}