比赛 20150421 评测结果 C
题目名称 飞越原野 最终得分 0
用户昵称 Satoshi 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2015-04-21 11:24:52
显示代码纯文本
#include <fstream>
#include <deque>
#include <string>
using namespace std;
ifstream in("escapea.in");
ofstream out("escapea.out");
struct node
{
	int x,y,p;
};
int m,n,d;
bool h[151][151];//湖泊or沼泽
int visit[121][121][121];//是否访问过
int dir[4][2]={{0,1},{0,-1},{-1,0},{1,0}};//向量
deque<node> q;
bool SPFA(int x,int y,int p)//判断是否访问过
{
	if(x>=1&&x<=m&&y>=1&&y<=n&&!visit[x][y][p])return 1;
	return 0;
}
int main()
{
	int i,j,size;
	node tmp,tmp2;
	char couple;
	long long ans=0;
	bool flag=0;
	in>>m>>n>>d;
	for(i=1;i<=m;i++)
	{
		for(j=1;j<=n;j++)
		{
			in>>couple;
			if(couple=='P')h[i][j]=0;
			if(couple=='T')h[i][j]=1;
		}
	}
	memset(visit,0,sizeof(visit));
	tmp.x=tmp.y=1;
	tmp.p=d;//初始状态,在(1,1),能量为d
	visit[tmp.x][tmp.y][tmp.p]=1;
	q.push_back(tmp);
	while(!q.empty())
	{
		size=q.size();
		while(size--)
		{
			tmp=q.front();
			q.pop_front();
			if(tmp.x==m&&tmp.y==n)
			{
				//out<<"fuck"<<endl;
				flag=1;
				break;
			}
			for(i=0;i<4;i++)//不飞行
		    {
			    tmp2.x=tmp.x+dir[i][0];
			    tmp2.y=tmp.y+dir[i][1];
			    tmp2.p=tmp.p;
			    if(SPFA(tmp2.x,tmp2.y,tmp2.p))
			    {
				    visit[tmp2.x][tmp2.y][tmp2.p]=1;
				    q.push_back(tmp2);
			    }
		    }
		    for(i=0;i<4;i++)//横向,竖向,斜向
		    {
			    for(j=0;j<=tmp.p;j++)
			    {
				tmp2.x=tmp.x+dir[i][0]*j;
				tmp2.y=tmp.y+dir[i][1]*j;
				tmp2.p=tmp.p-j;//消耗能量
				if(SPFA(tmp2.x,tmp2.y,tmp2.p))
				{
					visit[tmp2.x][tmp2.y][tmp2.p]=1;
					q.push_back(tmp2);
				}
				}
			}
		}
		if(flag==1)break;
		ans++;
	}
	if(flag)out<<ans<<endl;
	else out<<"impossible"<<endl;
	return 0;
}