Knight Match Play

Time Limit: 1000 MS Memory Limit: 65536 K Total Submit: 31(5 users) Total Accepted: 5(4 users) Rating:  Special Judge: No

Description

There are two knight teams, they have N and M knights respectively. The knights are numbered from 1 to N and 1 to M in their own team. They are trapped in a W*H grid puzzle. The puzzle only has four exituses which are the four corners of the puzzle. Only the directions up,down,left,right could the knight move to and the time move from one grid to the adjacent is fixed. They can form a "fight partner" if two knights sufficing the following conditions:1, The two knights come from different teams.2, Both of them can arrive to one of the exituses.3, The least time need to arrive to one of the exituses is same. So how many "fight partners" they can form? For this action, the leader gives the follow directives:1, Each team renumbering the knights with their least time need to use to get out of the puzzle. So the one who use the least time will get the ID 1 and the one use the most time will get the ID N or M. If some of them use the same time, then whose original ID is lower, who will get a lower ID.2, The chosen knights from the same team should have the continuous ID.3, Form "fight partners" according to the IDs one by one. That is to say the one has the lowest ID should form with the one has the lowest ID in another team, and so on.

Input

There are several test cases. The input of every test case are described as below.First line, there are four integers N,M,W,H. (0<n,m<300, 10<w,h<50). Then there are H lines, each line with W characters indicate for the puzzle. A character of '.' indicate the grid is empty, every empty grid could contain infinitely of knights. A character of '#' means the grid has a barrier and none knight can step into it. The four corners are empty. Then there N+M lines, each line with a pair of integers (x,y)(0<=x<h,0<=y<w) originally. The input will finish with the end of file

Output

An integer indicate for the maximal number of "fight partner" they can form.

Sample Input

4 3 7 6.#...#...#.............#........##..##....1 34 22 21 53 54 33 0

Sample Output

3

Source

Hunan University 2011 the 7th PRogramming Contest

Recommend

萬祥

題目大意：

給你一個H*W大小的一個迷宮，其中#表示不能走，“.”表示可以走，

現在迷宮的出口在四個角落（左上.左下.右上.右下）；

我們規定一共有兩活人，一伙N個，一伙M個，初始的時候編號按照輸入順序編號.

現在規定合作伙伴：

①合作伙伴是兩個人，并且來自不同的陣營。

②兩個人到達其最近的出口耗時相同。

然后我們需要將兩個陣營的騎士重新編號。

重新編號的規則按照：按照逃出迷宮從小到大的時間排序，然后按照這個順序從新編號。對于時間相同的，按照原序列優先級編號。

然后得到兩個重新編號的數組A.B.讓你在任意一個數組中取任意一段連續子序列，讓其是另外一個數組的子串，求這個合法子段的最長長度。

思路：

1、根據手動測試數據范圍已知，n，m不大于300.W.H不大于500.

2、題目很復雜，我們首先簡化問題，其實就是讓你①先求出每個人逃出迷宮的時間，然后按照時間點從小到大排序得到兩個數組，②然后求一個數組任意取一段連續子段是另外一個數組的子串即可，我們需要求一個最大長度。

3、那么我們首先處理前部分任務：

我們對于一個圖的遍歷的時間復雜度是O（nm）如果我們對于每一個騎士進行Bfs，肯定是超時的，那么我們Bfs四個起點，維護一個數組step【i】【j】.表示從任意起點到（i，j）這個位子的最短時間消耗，反過去考慮，step【i】【j】其實就是從（i，j）這一點，到任意出口的最小時間花費。

那么對于每個騎士來講，其逃出的時間，就是step【x】【y】；

這部分時間復雜度:O(nm);

4、然后我們處理后置任務。

①對于我們處理出來的兩個數組，按照時間從小到大先排個序，模擬題目要求。

②考慮到KMP匹配的特性，我們只需O（n）枚舉A.B數組中較小的那個序列的起點，去匹配另一個序列即可，過程維護一個最大匹配長度值。

③這里有一個trick.輸入數據不保證一個點一定能夠走到出口。所以從小到大排序結束之后，要重新界定一下數組的大小（就是要把不能走到終點的那些去除掉）。

④過程維護一個最大值即可。

時間復雜度O(min（lena，lenb）*（lena+lenb）)；

5、總體來說題目比較綜合，而且坑點十足，尼瑪對拍數據都調了很久才過，給這個題一個好評吧，估計也沒幾個人能做這個題了（- -）；

Ac代碼：

#include<stdio.h>#include<string.h>#include<algorithm>#include<queue>using namespace std;struct node{    int x,y;}now,nex;char mp[505][505];int step[505][505];int numa[505];int numb[505];int fx[4]={0,0,1,-1};int fy[4]={1,-1,0,0};int a[500];int b[500];int naxt[2500];int conta,contb,n,m;int lena,lenb;int Bfs(){    queue<node >s;    for(int i=0;i<n;i++)    {        for(int j=0;j<m;j++)        {            step[i][j]=0x3f3f3f3f;            if((i==0&&j==0)||(i==n-1&&j==m-1)||(i==n-1&&j==0)||(i==0&&j==m-1))            {                now.x=i;                now.y=j;                step[i][j]=0;                s.push(now);            }        }    }    while(!s.empty())    {        now=s.front();        s.pop();        for(int i=0;i<4;i++)        {            nex.x=now.x+fx[i];            nex.y=now.y+fy[i];            if(nex.x>=0&&nex.x<n&&nex.y>=0&&nex.y<m&&mp[nex.x][nex.y]!='#')            {                if(step[nex.x][nex.y]>step[now.x][now.y]+1)                {                    step[nex.x][nex.y]=step[now.x][now.y]+1;                    s.push(nex);                }            }        }    }    return 0;}void set_naxt()//子串的naxt數組{    int i=0,j=-1;    naxt[0]=-1;    while(i<lenb)    {        if(j==-1||b[i]==b[j])        {            i++; j++;            naxt[i]=j;        }        else        j=naxt[j];    }}int KMP(){    int maxnlen=0;    int i=0,j=0;    set_naxt();    while(i<lena)    {        if(j==-1||a[i]==b[j])        {            i++;j++;            maxnlen=max(j,maxnlen);        }        else        {            maxnlen=max(j,maxnlen);            j=naxt[j];        }        if(j==lenb)        {            return lenb;        }    }    return maxnlen;}int main(){    while(~scanf("%d%d%d%d",&conta,&contb,&m,&n))    {        for(int i=0;i<n;i++)scanf("%s",mp[i]);        Bfs();        for(int i=0;i<conta;i++)        {            int x,y;            scanf("%d%d",&x,&y);            numa[i]=step[x][y];        }        for(int i=0;i<contb;i++)        {            int x,y;            scanf("%d%d",&x,&y);            numb[i]=step[x][y];        }        sort(numa,numa+conta);        sort(numb,numb+contb);        for(int i=0;i<conta;i++)        {            if(numa[i]==0x3f3f3f3f)            {                conta=i;                break;            }        }        for(int i=0;i<contb;i++)        {            if(numb[i]==0x3f3f3f3f)            {                contb=i;                break;            }        }        int output=0;        if(conta<contb)        {            lena=contb;            for(int i=0;i<contb;i++)            {                a[i]=numb[i];            }            for(int i=0;i<conta;i++)            {                lenb=0;                for(int j=i;j<conta;j++)                {                    b[lenb++]=numa[j];                }                output=max(KMP(),output);            }        }        else        {            lena=conta;            for(int i=0;i<conta;i++)            {                a[i]=numa[i];            }            for(int i=0;i<contb;i++)            {                lenb=0;                for(int j=i;j<contb;j++)                {                    b[lenb++]=numb[j];                }                output=max(KMP(),output);            }        }        printf("%d/n",output);    }}