Submission #32163

---

Source Code Expand

#include<queue>
#include<cstdio>
#include<cstdlib>
#include"porter.h"

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

const int INF=1<<29;

int L,S,sx,sy;

void init(int L,int S){
	::L=L;
	::S=S;
	sx=sy=0;
}

void go_x(int &x,int &y,int &k,int d){
	if(d==0) return;

	if(d>0){ // 東
		if(k==0){
			if(x<L-1) x++;
			else      x=0, k=1;
		}
		else{
			if(x<S-1)       x++;
			else if(S-L<=y) x=0, y-=S-L, k=0;
			else            x=0, y+=L;
		}
	}
	else{ // 西
		if(k==0){
			if(x>0) x--;
			else    x=S-1, y+=S-L, k=1;
		}
		else{
			if(x>0) x--;
			else if(y<L) x=L-1, k=0;
			else         x=S-1, y-=L;
		}
	}
}

void go_y(int &x,int &y,int &k,int d){
	if(d==0) return;

	if(d>0){ // 北
		if(k==0){
			if(y<L-1) y++;
			else      y=0, x+=S-L, k=1;
		}
		else{
			if(y<S-1)     y++;
			else if(L<=x) y=0, x-=L;
			else          y=0, k=0;
		}
	}
	else{ // 南
		if(k==0){
			if(y>0) y--;
			else    y=S-1, k=1;
		}
		else{
			if(y>0)        y--;
			else if(x<S-L) y=S-1, x+=L;
			else           y=L-1, x-=S-L, k=0;
		}
	}
}

int moveTo(int tx,int ty,int a,int b){
	int dx[]={a,-b,-a,b};
	int dy[]={b,a,-b,-a};

	static int d[2][1000][1000]; // d[0]: 陸, d[1]: 海
	rep(k,2) rep(i,S) rep(j,S) d[k][i][j]=INF;
	d[0][sy][sx]=0;

	queue< pair<pair<int,int>,int> > Q;
	Q.push(make_pair(make_pair(sx,sy),0));
	while(!Q.empty()){
		int x=Q.front().first.first,y=Q.front().first.second,k=Q.front().second;
		Q.pop();

		rep(i,4){
			int x2=x,y2=y,k2=k;
			rep(j,abs(dx[i])) go_x(x2,y2,k2,dx[i]);
			rep(j,abs(dy[i])) go_y(x2,y2,k2,dy[i]);
			if(d[k2][y2][x2]==INF){
				d[k2][y2][x2]=d[k][y][x]+1;
				Q.push(make_pair(make_pair(x2,y2),k2));
			}
		}
	}

	sx=tx;
	sy=ty;

	return d[0][ty][tx]<INF?d[0][ty][tx]:-1;
}

Submission Info

Judge Result