3170.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Source

Problem Id:3170  User Id:fzk 
Memory:4544K  Time:421MS
Language:G++  Result:Accepted

Source 

#include <stdio.h>

bool set[2][1000][1000];
int q[1000000];
int map[1000][1000];
int n, m;

bool inmap( int x, int y ) {
	return 0<=x && x<n && 0<=y &&y <m;
}
const int dx[] = { 0, 0, 1, -1 };
const int dy[] = { 1, -1, 0, 0 };

int doit( int x, int y ) {
	int qh = 0, qe = 0, i, xx, yy;
	int count = 0, status, key;


	q[ qe++ ] = (x<<10) | y;
	q[ qe++ ] = -1;

	while( 1 ) {
		status = q[ qh++ ];
		if( status < 0 ) {
			count++;
			q[ qe++ ] = -1;
			continue;
		}

		x = ( status >>10 ) & 1023;
		y = status & 1023;
		key = status >> 20;

		for( i=0; i<4; i++ ) {
			if( inmap( xx=x+dx[i], yy=y+dy[i] ) && !set[key][xx][yy] ) {
				
				if( map[xx][yy] == 0 ) {
					set[key][xx][yy] = true;
					q[ qe++ ] = (key<<20) | (xx<<10) | yy;
				}
				else if( map[xx][yy] == 4 ) {
					set[true][xx][yy] = true;
					q[ qe++ ] = (1<<20) | (xx<<10) | yy;
				}
				else if( key && map[xx][yy] == 3 )
					return count+1;
			}
		}
	}
	return -1;
}

int main( ) {
	int i, j, bx, by;
	
	scanf( "%d%d", &m, &n);

	for( i=0; i<n; i++ ) {
		for( j=0; j<m; j++ ) {
			scanf( "%d", &map[i][j] );
			if( map[i][j] == 2 ) {
				bx = i, by = j;
				map[i][j] = 0;
			}
		}
	}
	printf( "%d\n", doit( bx, by ) );

	return 0;
}