3182.txt

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

Source

Problem Id:3182  User Id:fzk 
Memory:92K  Time:0MS
Language:C++  Result:Accepted

Source 

#include <stdio.h>
#include <memory.h>
#include <math.h>

char map[51][51];
char tmp[51][51];
int dis1[51][51];
int dis2[51][51];
int q[2500], qh, qe, n, m;

const int dx[] = { 0, 0, 1, -1, 1, 1, -1, -1 };
const int dy[] = { 1,-1, 0,  0, 1, -1, 1, -1 };

inline bool inmap( int x, int y ) {
	return x >= 0 && x < n && y >= 0 && y < m;
}

void bfs( int x, int y, int dis[51][51] ) {
	int xx, yy, i;
	qe = 1;
	qh = 0;
	q[0] = (x<<8)|y;
	dis[x][y] = 0;

	while( qh < qe ) {
		x = q[qh]>>8;
		y = q[qh]&((1<<8)-1);
		qh++;
		for( i=0; i<8; i++ ) 
		if( inmap( xx=x+dx[i], yy=y+dy[i] ) && tmp[xx][yy] != 'X' && dis[xx][yy] == -1 ) {
			dis[xx][yy] = dis[x][y] + 1;
			q[qe++] = (xx<<8)|yy;
		}
	}
}

int main( ) {
	int i, j, a, b, c, d, k, x, y, ans;
	scanf( "%d%d", &n, &m );
	memset( dis1, -1, sizeof dis1 );
	memset( dis2, -1, sizeof dis2 );
	c = -1;

	for( i=0; i<n; i++ ) {
		scanf( "%s", map[i] );
		for( j=0; j<m; j++ )
			if( map[i][j] == '*' )
				a = i, b = j;
	}
	for( i=0; i<n; i++ )
	for( j=0; j<m; j++ )
		if( map[i][j] == 'X' && ( c == -1 || abs(a-c)+abs(b-d)<abs(a-i)+abs(b-j) ) )
			c = i, d = j;

	for( i=0; i<n; i++ )
	for( j=0; j<m; j++ )
		if( (a-i)*(d-j)-(c-i)*(b-j) >= 0 )
			tmp[i][j] = map[i][j];
		else
			tmp[i][j] = 'X';
	bfs( a, b, dis1 );

	for( i=0; i<n; i++ )
	for( j=0; j<m; j++ )
		if( (a-i)*(d-j)-(c-i)*(b-j) <= 0 )
			tmp[i][j] = map[i][j];
		else
			tmp[i][j] = 'X';
	bfs( a, b, dis2 );
	
	ans = 10000;

	for( i=0; i<n; i++ )
	for( j=0; j<m; j++ )
		if( abs(i-a)+abs(j-b) > abs(c-a)+abs(d-b) && dis1[i][j] >= 0 )
			for( k=0; k<8; k++ ) {
				if( inmap( x=i+dx[k], y=j+dy[k]) && dis2[x][y] >=0 
					&& dis1[i][j] + dis2[x][y] + 1 <= ans )
					ans = dis1[i][j] + dis2[x][y] + 1;
			}
	printf( "%d\n", ans );

	return 0;
}