比赛中非常水的一道题，结束时大家才做。。没提交上。。泪奔。。
View Code
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<iostream> #include<algorithm> #include<map> #include<math.h> #include<queue> using namespace std; int N,M,C,n, maxn; int xx[]={1,0,0,-1}; int yy[]={0,1,-1,0}; char mp[5001][5001]; bool visit[5001][5001]; struct node { int x; int y; int cost; }S, P[510]; int jugde( int x, int y ) { if( x < 1 || x > N || y < 0 || y >= M ) return 0; return 1; } void bfs( ) { maxn = 0x7f7f7f7f; queue<node>p; p.push( S ); while( !p.empty() ) { node px = p.front(); p.pop(); int x = px.x; int y = px.y; int c = px.cost; for( int i = 0; i < 4; i++) { int x1 = x + xx[i]; int y1 = y + yy[i]; int dis = 0; if( visit[x1][y1] ) continue; if( !jugde(x1,y1) ) continue; if( mp[x1][y1] == 'C' ) { maxn = min( c, maxn ); break; //continue; } else if( mp[x1][y1] == '*' ) { visit[x1][y1] = 1; dis = c + C; node pt; pt.x = x1; pt.y = y1; pt.cost = dis; p.push( pt ); } else if( mp[x1][y1] == 'P' ) { for( int j = 0; j < n; j++) { visit[P[j].x][P[j].y] = 1; P[j].cost = c; p.push(P[j]); } visit[x1][y1] = 1; } } } if( maxn == 0x7f7f7f7f ) puts("Damn teoy!"); else printf("%d\n",maxn); } int main( ) { while( scanf("%d%d%d", &N, &M, &C) != EOF) { n = 0; for( int i = 0; i <= N; i++) for( int j = 0; j <= M; j++) visit[i][j] = 0; for( int i = 1; i <= N; i++) cin>>mp[i]; for( int i = 1; i <= N; i++) { for( int j = 0; j < M; j++) { if( mp[i][j] == 'Y' ) { S.x = i; S.y = j; S.cost = 0; } else if( mp[i][j] == 'P') { P[n].x = i; P[n].y = j; P[n].cost = 0; n++; } } } bfs( ); } return 0; }