自作問題 - yanprog @ ウィキ

(x1,y1)の位置から(y1,y2)まで、移動するのに必要な最小のステップ数を求める。
１ステップで、上下左右のどれかにすすめる。
xs,ysは進めない升目のリスト。

#include <cstdio>
#include <cstdlib>
//#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <assert.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
 
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
 
#define clr(a) memset((a),0,sizeof(a))
#define nclr(a) memset((a),-1,sizeof(a))
#define pb push_back
 
double pi=3.14159265358979323846;
 
using namespace std;
static const double EPS = 1e-5;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;
 
template<typename T> std::ostream& operator<<(std::ostream& os, const vector<T>& z){
	os << "[ ";
	REP(i,z.size())os << z[i] << ", " ;
	return ( os << "]" << endl);
}
 
template<typename T> std::ostream& operator<<(std::ostream& os, const set<T>& z){
	os << "set( "; 
	EACH(p,z)os << (*p) << ", " ;
	return ( os << ")" << endl);
}
 
template<typename T,typename U> std::ostream& operator<<(std::ostream& os, const map<T,U>& z){
	os << "{ "; 
	EACH(p,z)os << (p->first) << ": " << (p->second) << ", " ;
	return ( os << "}" << endl);
}
 
template<typename T,typename U> std::ostream& operator<<(std::ostream& os, const pair<T,U>& z){
	return ( os << "(" << z.first << ", " << z.second << ",)" );
}
 
//x^y%d
int powmod(int x,int n,int d){
  if(n==0)return 1;
  int s=x%d,t=x%d,u=n-1;
  while(u){
    if(u%2) s=(s*t)%d;
    t=(t*t)%d;
    u/=2;
  }
  return s;
}
 
ll getl(){
  ll ret;
  scanf("%I64d", &ret);
  return ret;
}
 
int xn;
 
int pfromxy(int x, int y){
	return x+xn*y;
}
int xfromp(int p){
	return p%xn;
}
int yfromp(int p){
	return p/xn;
}
 
typedef pair<ll, int> pli;
 
int xfi[4]={1,0,-1,0}, yfi[4]={0,1,0,-1};
 
template<typename T1, typename T2, typename T3 > struct trip{
	T1 t1;
	T2 t2;
	T3 t3;
	trip(T1 _t1, T2 _t2, T3 _t3){
		t1=_t1;
		t2=_t2;
		t3=_t3;
	}
	bool operator<(trip<T1,T2,T3> t){
		return t1<t.t1;
	}
};
 
ll cal(ll x1, ll y1, ll x2, ll y2, const vl &blockx, const vl &blocky){
	set<ll> xss, yss;
	for(int i=0;i<blockx.size();i++){
		for(int d=-1;d<=1;d++){
			xss.insert(blockx[i]+d);
			yss.insert(blocky[i]+d);
		}
	}
	for(int d=-1;d<=1;d++){
		xss.insert(x1+d);
		xss.insert(x2+d);
		yss.insert(y1+d);
		yss.insert(y2+d);
	}
	vl xs(xss.begin(), xss.end());
	vl ys(yss.begin(), yss.end());
	map<ll,int> bxs, bys;
	for(int i=0;i<xs.size();i++){
		bxs[xs[i]]=i;
	}
	for(int i=0;i<ys.size();i++)bys[ys[i]]=i;
	xn=xs.size();
	vvl z(xs.size());
	for(int i=0;i<xs.size();i++){
		for(int j=0;j<ys.size();j++){
			z[i].pb(-1LL);
		}
	}
	for(int i=0;i<blockx.size();i++){
		ll x=blockx[i], y=blocky[i];
		int ix=bxs[x], iy=bys[y];
		z[ix][iy]=-2;
	}
	int gx1=bxs[x1], gy1=bys[y1];
	int gx=bxs[x2], gy=bys[y2];
	priority_queue<pli , vector<pli>, greater<pli> > pq;
	pq.push(pli(0, pfromxy(gx1,gy1) ));
	debug(gx1);debug(gy1);debug(gx);debug(gy);
	debug(xs);debug(ys);
	debug(z);
	while(!pq.empty()){
		pli pd=pq.top();
		pq.pop();
		ll d=pd.first;
		ll p=pd.second;
		int x=xfromp(p), y=yfromp(p);
		if(x==gx && y==gy){
			debug(z);
			return d;
		}
		if(z[x][y]!=-1)continue;
		z[x][y]=d;
		if(1){
			for(int r=0;r<4;r++){
				int dx=xfi[r], dy=yfi[r];
				int nx=x+dx, ny=y+dy;
				if(!(0<=nx && nx<xs.size() && 0<=ny && ny<ys.size()))continue;
				int np=pfromxy(nx,ny);
				ll nd=d+abs(xs[nx]-xs[x])+abs(ys[ny]-ys[y]);
				pq.push(pli(nd,np));
			}
		}
	}
	return -1;
}
 
void test(){
	ll x1=0, y1=0, x2=10000, y2=10000;
	int hxs[3]={x2,500,x2-1}, hys[3]={y2-1,500,y2};
	vl xs(hxs, hxs+3), ys(hys, hys+3);
	debug(cal(x1,y1,x2,y2,xs,ys));
	return;
}
 
int main(){
	test();
  return 0;
}