记录编号	46593	评测结果	AAAAA
题目名称	城市街道交通费系统	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2012-10-28 21:29:54	内存使用	3.39 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;

//0	dong	East
//1	xi		West
//2	nan		South
//3	bei		North

const short RUL[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
const short COST[4][4]={
/*     E  W  S  N     */
/*E*/{00,10,05,01},
/*W*/{10,00,01,05},
/*S*/{01,05,00,10},
/*N*/{05,01,10,00},};

char map[110][110];
int f[4][110][110];
bool used[4][110][110];

int minint(int a,int b)
{
	if (a<b)
		return(a);
	return(b);
}

int main(void)
{
	freopen("erp.in","r",stdin);
	freopen("erp.out","w",stdout);
	int i,j,k,l,n,m,xe,ye,xs,ys,xt,yt,costnow,templ;
	bool un=true,succ,zero;
	cin>>n>>m;
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++)
		{
			for (k=0;k<4;k++)
				f[k][i][j]=~0u>>1;
			cin>>map[i][j];
			if (map[i][j]=='F')
			{
				xe=i;
				ye=j;
				map[i][j]='#';
			}
			else if (map[i][j]!='#'&&map[i][j]!='.')
			{
				xs=i;
				ys=j;
				if (map[i][j]=='E')
				{
					f[0][i][j]=0;
				}
				else if (map[i][j]=='W')
				{
					f[1][i][j]=0;
				}
				else if (map[i][j]=='S')
				{
					f[2][i][j]=0;
				}
				else if (map[i][j]=='N')
				{
					f[3][i][j]=0;
				}
				map[i][j]='#';
			}
		}
	costnow=0;
	while (un)
	{
		zero=false;
		for (i=1;un&&i<=n;i++)
			for (j=1;un&&j<=m;j++)
				for (k=0;k<4;k++)
					if (f[k][i][j]==costnow)
					{
						if (i==xe&&j==ye)
							un=false;
						if (!un)
							break;
						if (used[k][i][j])
							continue;
						used[k][i][j]=true;
						succ=false;
						for (l=0;l<4;l++)
						{
							if (COST[k][l]==10)
							{
								templ=l;
								continue;
							}
							xt=i+RUL[l][0];
							yt=j+RUL[l][1];
							if (map[xt][yt]=='.')
								continue;
							succ=true;
							while (map[xt][yt]=='#')
							{
								if (f[l][xt][yt]>f[k][i][j]+COST[k][l])
								{
									f[l][xt][yt]=f[k][i][j]+COST[k][l];
									used[l][xt][yt]=false;
								}
								if (f[l][xt][yt]==f[k][i][j])
									zero=true;
								xt+=RUL[l][0];
								yt+=RUL[l][1];
							}
						}
						if (!succ)
						{
							xt=i+RUL[templ][0];
							yt=j+RUL[templ][1];
							if (map[xt][yt]=='.')
								continue;
							while (map[xt][yt]=='#')
							{
								f[templ][xt][yt]=minint(f[templ][xt][yt],f[k][i][j]+COST[k][templ]);
								xt+=RUL[templ][0];
								yt+=RUL[templ][1];
							}
						}
					}
		if (!zero)
			costnow++;
	}
	cout<<minint(minint(f[0][xe][ye],f[1][xe][ye]),minint(f[2][xe][ye],f[3][xe][ye]))<<endl;
	return(0);
}