「CF413E」Maze 2D

2014年4月24日4,4464

The last product of the R2 company in the 2D games’ field is a new revolutionary algorithm of searching for the shortest path in a 2 × nmaze.

Imagine a maze that looks like a 2 × n rectangle, divided into unit squares. Each unit square is either an empty cell or an obstacle. In one unit of time, a person can move from an empty cell of the maze to any side-adjacent empty cell. The shortest path problem is formulated as follows. Given two free maze cells, you need to determine the minimum time required to go from one cell to the other.

Unfortunately, the developed algorithm works well for only one request for finding the shortest path, in practice such requests occur quite often. You, as the chief R2 programmer, are commissioned to optimize the algorithm to find the shortest path. Write a program that will effectively respond to multiple requests to find the shortest path in a 2 × n maze.

Input

The first line contains two integers, n and m (1 ≤ n ≤ 2·105; 1 ≤ m ≤ 2·105) — the width of the maze and the number of queries, correspondingly. Next two lines contain the maze. Each line contains n characters, each character equals either ‘.‘ (empty cell), or ‘X‘ (obstacle).

Each of the next m lines contains two integers vi and ui (1 ≤ vi, ui ≤ 2n) — the description of the i-th request. Numbers vi, ui mean that you need to print the value of the shortest path from the cell of the maze number vi to the cell number ui. We assume that the cells of the first line of the maze are numbered from 1 to n, from left to right, and the cells of the second line are numbered from n + 1 to 2n from left to right. It is guaranteed that both given cells are empty.

Output

Print m lines. In the i-th line print the answer to the i-th request — either the size of the shortest path or -1, if we can’t reach the second cell from the first one.

Sample test(s)

input

4 7

.X..

...X

5 1

1 3

7 7

1 4

6 1

4 7

5 7

output

input

10 3
X...X..X..
..X...X..X
11 7
7 18
18 10

10 3

X...X..X..

..X...X..X

11 7

7 18

18 10

output

9
-1
3

-1

题解

题意是给一张2*n的地图，有一些X不能走，问一个点到另一个的最短路

我原来以为是dp。。。

后来发现各种细节跪到最后

orz卓神线段树秒杀，维护l-r区间内两行格子，四个角之间的距离

#include<iostream>
#include<cstdio>
#include<cstring>
#define N 200001
#define M 600001
#define inf 500000000
using namespace std;
int n,m;
int mp[3][N];
char ch[N];
struct data{int d1,d2,d3,d4;};
struct segtree{int l,r;data d;}t[M];
//左上到右上，左上到右下，左下到右上，左下到右下
data merge(data a,data b)
{
	data tmp;
	tmp.d1=min(inf,min(a.d1+b.d1,a.d2+b.d3)+1);
	tmp.d2=min(inf,min(a.d1+b.d2,a.d2+b.d4)+1);
	tmp.d3=min(inf,min(a.d3+b.d1,a.d4+b.d3)+1);
	tmp.d4=min(inf,min(a.d3+b.d2,a.d4+b.d4)+1);
	return tmp;
}
void build(int k,int l,int r) 
{
	t[k].l=l;t[k].r=r;
	if(l==r)
	{
		t[k].d.d1=t[k].d.d2=t[k].d.d3=t[k].d.d4=inf;
		if(mp[1][l])t[k].d.d1=0;
		if(mp[2][l])t[k].d.d4=0;
		if(mp[1][l]&&mp[2][l])t[k].d.d2=t[k].d.d3=1;
		return;
    }
    int mid=(l+r)>>1;
    build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	t[k].d=merge(t[k<<1].d,t[k<<1|1].d);
}
data query(int k,int x,int y)
{
	int l=t[k].l,r=t[k].r;
	if(x==l&&y==r)return t[k].d;
	int mid=(l+r)>>1;
	if(mid>=y)
	   return query(k<<1,x,y);
    else if(mid<x)
       return query(k<<1|1,x,y);
    else 
   	return merge(query(k<<1,x,mid),query(k<<1|1,mid+1,y));
}
int ask(int x,int y)
{
	int a=(x-1)%n+1,b=(y-1)%n+1;
	if(a>b){swap(x,y);swap(a,b);}
	data tmp=query(1,a,b);
	if(x<=n&&y<=n)return tmp.d1;
	if(x<=n&&y>n)return tmp.d2;
	if(x>n&&y<=n)return tmp.d3;
	if(x>n&&y>n)return tmp.d4;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=2;i++)
    {
    	scanf("%s",ch);
    	for(int j=1;j<=n;j++)
    	   if(ch[j-1]=='.')mp[i][j]=1;
    }
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
    	int x,y;
    	scanf("%d%d",&x,&y);
    	int ans=ask(x,y);
    	if(ans<inf)printf("%d\n",ans);
    	else printf("-1\n");
    }
	return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#define N 200001

#define M 600001

#define inf 500000000

using namespace std;

int n,m;

int mp[3][N];

char ch[N];

struct data{int d1,d2,d3,d4;};

struct segtree{int l,r;data d;}t[M];

//左上到右上，左上到右下，左下到右上，左下到右下

data merge(data a,data b)

{

data tmp;

tmp.d1=min(inf,min(a.d1+b.d1,a.d2+b.d3)+1);

tmp.d2=min(inf,min(a.d1+b.d2,a.d2+b.d4)+1);

tmp.d3=min(inf,min(a.d3+b.d1,a.d4+b.d3)+1);

tmp.d4=min(inf,min(a.d3+b.d2,a.d4+b.d4)+1);

return tmp;

}

void build(int k,int l,int r)

{

t[k].l=l;t[k].r=r;

if(l==r)

{

t[k].d.d1=t[k].d.d2=t[k].d.d3=t[k].d.d4=inf;

if(mp[1][l])t[k].d.d1=0;

if(mp[2][l])t[k].d.d4=0;

if(mp[1][l]&&mp[2][l])t[k].d.d2=t[k].d.d3=1;

return;

}

int mid=(l+r)>>1;

build(k<<1,l,mid);

build(k<<1|1,mid+1,r);

t[k].d=merge(t[k<<1].d,t[k<<1|1].d);

}

data query(int k,int x,int y)

{

int l=t[k].l,r=t[k].r;

if(x==l&&y==r)return t[k].d;

int mid=(l+r)>>1;

if(mid>=y)

return query(k<<1,x,y);

else if(mid<x)

return query(k<<1|1,x,y);

else

return merge(query(k<<1,x,mid),query(k<<1|1,mid+1,y));

}

int ask(int x,int y)

{

int a=(x-1)%n+1,b=(y-1)%n+1;

if(a>b){swap(x,y);swap(a,b);}

data tmp=query(1,a,b);

if(x<=n&&y<=n)return tmp.d1;

if(x<=n&&y>n)return tmp.d2;

if(x>n&&y<=n)return tmp.d3;

if(x>n&&y>n)return tmp.d4;

}

int main()

{

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

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

{

scanf("%s",ch);

for(int j=1;j<=n;j++)

if(ch[j-1]=='.')mp[i][j]=1;

}

build(1,1,n);

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

{

int x,y;

scanf("%d%d",&x,&y);

int ans=ask(x,y);

if(ans<inf)printf("%d\n",ans);

else printf("-1\n");

}

return 0;

}

« 「BZOJ3196」JoyOI 1730 二逼平衡树「BZOJ1984」月下“毛景树” »

zld3794955

Orz。。居然写得这么短。。本弱写的线段树长得跟狗一样T T

hzwer

因为我看了几眼你的代码2333

zld3794955

2333竟然能看得下去本弱的代码。。Orz。。

黑暗世界

orz 听说卓神暴虐我们黄学长大神？

hzwer.com _ Home | http://hzwer.com

「CF413E」Maze 2D

分类目录

热门文章

Myfriends

近期评论