[World Final 2005][Uva Live Archive] 3274 - Crossing Streets

題目網址: http://goo.gl/S1GSv3

題意: 你想從家裡出發至學校，題目給定N條馬路，馬路的兩端點皆為整數點，且馬路只會是水平或鉛直，但是你可以任意的走(不必在整數點上)，但是不能橫向穿越兩條馬路交點(誰敢直接對角過馬路阿XDDDD)，因為你怕危險，從家裡走至學校的路途中想經過盡量少的馬路，問最少需要多少馬路。



解法: 看到此種題目，第一件事通常是先離散化，原本題目為從起點至終點，穿過最少的線段，離散化後，題目則變為從起點點格至終點點格，穿過最少的點格牆。可以想像從起點倒水，若水被牆擋住就拆掉最外面那道牆，一直拆到水碰到終點，直接使用BFS來拆牆。

(PS: 我有看到較好的方法，是把離散化後的圖，若下個點是馬路則邊權重為1，若非，則是0，求從起點至終點的最短路徑。)

TAG: BFS, 離散化

注意: NA

程式碼:

	#include <iostream>
	#include <cstdio>
	#include <cstring>
	#include <algorithm>
	#include <queue>
	using namespace std;
	#define N 510
	#define clr(x,v) memset( x, v, sizeof(x) )
	struct Point {
	int x, y;
	Point( int _x = 0, int _y = 0 ): x(_x), y(_y) {}
	const bool operator==( const Point &op ) const { return (x==op.x&&y==op.y); }
	const Point operator+( const Point &op ) const { return Point(x+op.x,y+op.y); }
	Point go( const int dir ) const {
	switch( dir ) {
	case 0: return (*this)+Point(0,1);
	case 1: return (*this)+Point(1,0);
	case 2: return (*this)+Point(0,-1);
	case 3: return (*this)+Point(-1,0);
	default: return (*this);
	}
	}
	};
	struct State {
	Point p;
	int step;
	State( Point _p = Point(), int _step = 0 ): p(_p), step(_step) {}
	};
	typedef queue<Point> QP;
	typedef queue<State> QS;
	int n, ans, ti = 0;
	int dx[2*N], dy[2*N];
	int xlen, ylen;
	Point s, t;
	Point st[N][2];
	bool isWall[2*N][2*N];
	bool vis[2*N][2*N];
	bool inWQ[2*N][2*N];
	bool inNWQ[2*N][2*N];
	QS wq;
	QP nwq;
	bool over;
	int x_r2d( int x )
	{
	static int l, r, mid;
	l = 1; r = xlen;
	while( l <= r ) {
	mid = (l+r)>>1;
	if( dx[mid] == x ) return mid;
	if( dx[mid] > x ) r = mid-1;
	else l = mid+1;
	}
	}
	int y_r2d( int y )
	{
	static int l, r, mid;
	l = 1; r = ylen;
	while( l <= r ) {
	mid = (l+r)>>1;
	if( dy[mid] == y ) return mid;
	if( dy[mid] > y ) r = mid-1;
	else l = mid+1;
	}
	}
	void init( void )
	{
	int i, x, y;
	Point ns, nt;
	xlen = ylen = 0;
	for( i = 1; i <= n; ++i ) {
	scanf( "%d%d%d%d", &st[i][0].x, &st[i][0].y, &st[i][1].x, &st[i][1].y );
	dx[++xlen] = st[i][0].x; dx[++xlen] = st[i][1].x;
	dy[++ylen] = st[i][0].y; dy[++ylen] = st[i][1].y;
	}
	scanf( "%d%d%d%d", &s.x, &s.y, &t.x, &t.y );
	dx[++xlen] = s.x; dx[++xlen] = t.x;
	dy[++ylen] = s.y; dy[++ylen] = t.y;
	sort( dx+1, dx+1+xlen );
	sort( dy+1, dy+1+ylen );
	xlen = unique( dx+1, dx+1+xlen )-(dx+1);
	ylen = unique( dy+1, dy+1+ylen )-(dy+1);
	clr( isWall, 0 );
	clr( vis, 0 );
	clr( inWQ, 0 );
	clr( inNWQ, 0 );
	over = false;
	ans = 0;
	for( i = nwq.size(); i; --i ) nwq.pop();
	for( i = wq.size(); i; --i ) wq.pop();
	for( i = 1; i <= n; ++i ) {
	ns = Point( x_r2d(st[i][0].x), y_r2d(st[i][0].y) );
	nt = Point( x_r2d(st[i][1].x), y_r2d(st[i][1].y) );
	if( ns.x != nt.x ) {
	y = ns.y;
	if( ns.x < nt.x )
	for( x = ns.x; x <= nt.x; ++x ) isWall[x][y] = true;
	else
	for( x = nt.x; x <= ns.x; ++x ) isWall[x][y] = true;
	} else {
	x = ns.x;
	if( ns.y < nt.y )
	for( y = ns.y; y <= nt.y; ++y ) isWall[x][y] = true;
	else
	for( y = nt.y; y <= ns.y; ++y ) isWall[x][y] = true;
	}
	}
	s = Point( x_r2d(s.x), y_r2d(s.y) );
	t = Point( x_r2d(t.x), y_r2d(t.y) );
	/*
	for( x = 0; x <= xlen+1; ++x ) {
	for( y = 0; y <= ylen+1; ++y ) {
	if( s.x == x && s.y == y ) putchar('S');
	else if( t.x == x && t.y == y ) putchar('T');
	else {
	if( isWall[x][y] ) putchar('W');
	else putchar('_');
	}
	}
	putchar('\n');
	}
	*/
	//for( i = 1; i <= xlen; ++i ) printf( "%d ", dx[i] ); putchar('\n');
	//for( i = 1; i <= ylen; ++i ) printf( "%d ", dy[i] ); putchar('\n');
	}
	const bool valid( const Point &p )
	{
	return (0 <= p.x && p.x <= xlen+1 && 0 <= p.y && p.y <= ylen+1);
	}
	void dfs( const Point &now )
	{
	int i;
	Point next;
	//printf( "#dfs (%d,%d)\n", now.x, now.y );
	vis[now.x][now.y] = true;
	for( i = 0; i <= 3; ++i ) {
	next = now.go(i);
	if( valid(next) && !vis[next.x][next.y] ) {
	if( next == t ) {
	over = true;
	//printf( "(%d,%d) is over!\n", next.x, next.y );
	return ;
	} else if( isWall[next.x][next.y] ) {
	if( inWQ[next.x][next.y] ) continue;
	inWQ[next.x][next.y] = true;
	wq.push( State(next,1) );
	} else {
	dfs( next );
	}
	}
	}
	}
	int bfs( void )
	{
	int wlen = 0, i;
	State now, next;
	while( !wq.empty() ) {
	now = wq.front(); wq.pop();
	//printf( "@bfs (%d,%d)\n", now.p.x, now.p.y );
	vis[now.p.x][now.p.y] = true;
	wlen = max( wlen, now.step );
	for( i = 0; i <= 3; ++i ) {
	next = State( now.p.go(i), now.step+1 );
	if( valid(next.p) && !vis[next.p.x][next.p.y] ) {
	if( next.p == t ) {
	over = true;
	//printf( "(%d,%d) step %d is over!\n", next.p.x, next.p.y, now.step );
	return now.step;
	} else if( !isWall[next.p.x][next.p.y] ) {
	if( inNWQ[next.p.x][next.p.y] ) continue;
	inNWQ[next.p.x][next.p.y] = true;
	nwq.push(next.p);
	} else {
	if( inWQ[next.p.x][next.p.y] ) continue;
	wq.push( next );
	}
	}
	}
	}
	return wlen;
	}
	void solve( void )
	{
	int i;
	//printf( "! s(%d,%d) t(%d,%d)\n", s.x, s.y, t.x, t.y );
	int wlen;
	nwq.push(s);
	while( !over ) {
	while( !nwq.empty() ) {
	dfs( nwq.front() );
	nwq.pop();
	}
	if( over ) break;
	ans += bfs();
	}
	//puts("over");
	}
	void output( void )
	{
	printf( "City %d\n", ++ti );
	printf( "Peter has to cross %d streets\n", ans );
	}
	int main( void )
	{
	int i;
	while( scanf( "%d", &n ) == 1 && n ) {
	init();
	solve();
	output();
	}
	return 0;
	}

view raw 3274 - Crossing Streets.cpp hosted with ❤ by GitHub