2542120_ac_187ms_1264k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>
#include <queue>
#include <cctype>
#include <algorithm>
using namespace std;
#define INF 1000000

char map[101][101];
int n, l, ans;
int dis[101][101][26];

typedef struct node
{
	int day;
	int num;
	int i, j;
}pot;

queue <pot> que;

int valid(int i,int j)
{
	if(i<=0||i>=n||j<=0||j>=l)
		return 0;
	return 1;
}

int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};

void bfs()
{
	int i, j, k, num, day;
	int a, b;
	pot tmp, enq;

	ans = INF;
	for(i = 0; i < n; i++)
		for(j = 0; j < l; j++)
		{
			if(map[i][j]=='#'||isalpha(map[i][j]))
			{
				tmp.i = i,tmp.j = j;
				tmp.day = 0;
				tmp.num = (map[i][j]=='#')?0:map[i][j]-'A'+1;
				que.push(tmp);
			}
		}
	while(!que.empty())
	{
		tmp = que.front();
		que.pop();
		i = tmp.i;j = tmp.j;num = tmp.num;day = tmp.day;
	
		for(k = 0; k < 4; k++)
		{
			a = dir[k][0],b = dir[k][1];
			if(valid(i+a,j+b)&&map[i+a][j+b]!='*')
			{
				enq.i = i+a;enq.j = j+b;enq.num = num;
				if(map[i+a][j+b]=='.')
				{
					if(dis[i+a][j+b][num]>day)
					{
						dis[i+a][j+b][num] = day;
						enq.day =day;
						que.push(enq);
					}
				}
				if(map[i+a][j+b]=='$')
				{
					if(dis[i+a][j+b][num]>day)
					{
						dis[i+a][j+b][num] = day;
						enq.day = day;
						que.push(enq);
					}
					if(ans>day)
						ans = day;
				}
				if(isdigit(map[i+a][j+b]))
				{
					if(dis[i+a][j+b][num]>day+map[i+a][j+b]-'0')
					{
						enq.day = dis[i+a][j+b][num] = day+map[i+a][j+b]-'0';
						que.push(enq);
					}
					if(num)
					{
						enq.num = num-1;
						if(dis[i+a][j+b][num-1]>day)
						{
							enq.day = dis[i+a][j+b][num-1] = day;
							que.push(enq);
						}
					}
				}
			}
		}
	}
}

int main()
{
	char tmp[101];

	while(gets(tmp))
	{
		if(tmp[0]=='-')
			break;
		strcpy(map[0],tmp);
		l = strlen(map[0]);
		n = 1;
		while(gets(map[n]))
		{
			if(strcmp(map[n],"")==0)
				break;
			n++;
		}
		for(int i = 0; i < n; i++)
			for(int j = 0; j < l; j++)
				for(int  k = 0; k < 26; k++)
					dis[i][j][k] = INF;
		bfs();
		if(ans==INF)
			printf("IMPOSSIBLE\n");
		else
			printf("%d\n",ans);
	}
	return 0;
}