SRM 277 DIV1 Hard SafeJourney

問題 Editorial

問題

大きいマップに縦の道路と横の道路が最大600個くらいあるから道路を渡る回数を最小化して

解答

座標圧縮してBFS。
自分は道路の前後も座標に含めたらメモリがギリギリになってしまった。
含めるのは道路の座標そのものだけでいいらしい。他の人の解答参考。

コメント

座標圧縮に含める座標はきちんと考えるべき。
あとMLEのために、shortでいいならshortにしとけ。

コード

#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <sstream>
#include <cstring>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define each(it,o) for(__typeof((o).begin()) it = (o).begin(); it != (o).end(); ++ it)
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll; typedef vector<long long> vl;  
struct SafeJourney {
	void parse(string s, ll& x, ll& y) {
		stringstream ss(s);
		ss >> x >> y;
		x *= 2, y *= 2;
	}
	void transpos(map<ll,int>& m, vl& v) {
		each(i, v) *i = m[*i];
	}
	int fewestRoadCrossings(ll width, ll length, vector <string> horizontal, vector <string> vertical, string home, string work) {
		map<ll,int> ym, xm; int yn, xn; int top, left;
		vl hy, hx1, hx2, vx, vy1, vy2;
		ll sx, sy, ex, ey;
		static const int dy[4] = {0, 1, 0, -1}, dx[4] = {1, 0, -1, 0};

		length *= 2, width *= 2;
		ym[0] = xm[0] = ym[length] = xm[width] = -1;
		ym[-1] = xm[-1] = ym[length+1] = xm[width+1] = -1;
		each(i, horizontal) {
			each(j, *i) if(*j == ',') *j = ' ';
			stringstream ss(*i);
			ll y, x1, x2;
			while(ss >> y >> x1 >> x2) {
				y *= 2, x1 *= 2, x2 *= 2;
				hy.pb(y), hx1.pb(x1), hx2.pb(x2);
				ym[y] = xm[x1] = xm[x2] = -1;
				ym[y-1] = ym[y+1] = xm[x1+1] = -1;
			}
		}
		each(i, vertical) {
			each(j, *i) if(*j == ',') *j = ' ';
			stringstream ss(*i);
			ll x, y1, y2;
			while(ss >> x >> y1 >> y2) {
				x *= 2, y1 *= 2, y2 *= 2;
				vx.pb(x), vy1.pb(y1), vy2.pb(y2);
				xm[x] = ym[y1] = ym[y2] = -1;
				xm[x-1] = xm[x+1] = ym[y1+1] = -1;
			}
		}
		parse(home, sx, sy); parse(work, ex, ey);
		rer(e, -1, 1) xm[sx+e] = xm[ex+e] = ym[sy+e] = ym[ey+e];
		yn = 0; each(i, ym) i->second = yn ++;
		xn = 0; each(i, xm) i->second = xn ++;
		transpos(ym, hy); transpos(ym, vy1); transpos(ym, vy2);
		transpos(xm, vx); transpos(xm, hx1); transpos(xm, hx2);
		sy = ym[sy], sx = xm[sx];
		ey = ym[ey], ex = xm[ex];
		length = ym[length], width = xm[width];
		top = ym[0], left = xm[0];

//道路の判定用のマップを累積和の逆演算で作っている。(座標が少ないほかの人の解答の場合)普通にやってもいいようだ。
		static short hroad[2500][2500], vroad[2500][2500];
		mset(hroad, 0); mset(vroad, 0);
		rep(i, hy.size()) {
			hroad[hy[i]][hx1[i]] ++;
			hroad[hy[i]][hx2[i]+1] --;
		}
		rep(i, vx.size()) {
			vroad[vy1[i]][vx[i]] ++;
			vroad[vy2[i]+1][vx[i]] --;
		}
		rep(y, yn) { rep(x, xn) {
			hroad[y][x] += x == 0 ? 0 : hroad[y][x-1];
			vroad[y][x] += y == 0 ? 0 : vroad[y-1][x];
//			cout << (y<top||y>length||x<left||x>width ? '#' : sy==y&&sx==x ? 'H' : ey==y && ex==x ? 'W' : ".|-+"[(hroad[y][x]!=0)*2+(vroad[y][x]!=0)]);
		} //cout << endl;
		}

		static short memo[2500][2500];
		mset(memo, INF);
		deque<pair<pair<short,short>,short> > q;
		q.push_front(mp(mp(sy, sx), 0));
		while(!q.empty()) {
			pair<short,short> p = q.front().first; short dist = q.front().second; q.pop_front();
			short cy = p.first, cx = p.second;
			if(memo[cy][cx] <= dist) continue;
			memo[cy][cx] = dist;
			if(cy == ey && cx == ex) return dist;
			rep(dir, 4) {
				bool cross = 0;
				short ny = cy + dy[dir], nx = cx + dx[dir];
				if(ny < top || ny > length || nx < left || nx > width) continue;
				if(hroad[ny][nx] && vroad[ny][nx]) continue;
				if(hroad[ny][nx])
					ny += dy[dir], cross = 1;
				else if(vroad[ny][nx])
					nx += dx[dir], cross = 1;
				if(ny < top || ny > length || nx < left || nx > width) continue;
				if(!cross) q.push_front(mp(mp(ny, nx), dist));
				else q.push_back(mp(mp(ny, nx), dist + 1));
			}
		}
	}
};