记录编号	159428	评测结果	WAAAWWWWWA
题目名称	飞越原野	最终得分	40
用户昵称	wolf.	是否通过	未通过
代码语言	C++	运行时间	0.116 s
提交时间	2015-04-21 14:11:19	内存使用	0.33 MiB

#include<iostream>
#include<fstream>
#include<bitset>
#include<vector>
#include<deque>
#include<map>
#include<set>
#include<queue>
#include<string>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<cstdio>
using namespace std;
#if defined wolf
const string ok="OK";
const string kk="	";
ofstream nnew("escapea.in",ios::app);
ifstream fin("escapea.in");
#define fout cout
#define Endl endl
#else
ifstream fin("escapea.in");
ofstream fout("escapea.out");
#endif
class node{
public:
	int x,y;
	int ttime,k;
	node(){
		ttime=999999999;
		k=0;
	}
	node(int a,int b,int c,int d){
		x=a;
		y=b;
		ttime=c;
		k=d;
	}
	bool operator <(const node & x)const{
		return ttime>x.ttime;
	}
};
const int IMAX=999999999;
vector<vector<bool> > PP;
vector<vector<int> > point;
priority_queue<node> Q;
bool flag[105][105];
int core(int m,int n,int k){
	Q.push(node(0,0,0,k));
	while(!Q.empty()){
		node it=Q.top();
		point[it.x][it.y]=it.ttime;
		Q.pop();
		if(flag[it.x][it.y]){
			continue;
		}
		flag[it.x][it.y]=1;
		//cout<<it.x<<"  "<<it.y<<"  "<<it.ttime<<"  "<<it.k<<endl;
		if(it.x==m-1&&it.y==n-1){
			return it.ttime;
		}
		//走路//飞行
		int len=0;bool fall=1;
		for(int i=it.x+1;i<m;++i){
			++len;int j=it.y;
			if(len<=it.k){//飞行
				Q.push(node(i,j,it.ttime+1,it.k-len));
			}
			if(fall&&PP[i][j]){//步行
				if(point[i][j]>it.ttime+len){
					Q.push(node(i,j,it.ttime+len,it.k));
				}
			}else{
				fall=0;
			}
			
		}
		len=0;fall=1;
		for(int j=it.y+1;j<n;++j){
			++len;int i=it.x;
			if(len<=it.k){//飞行
				Q.push(node(i,j,it.ttime+1,it.k-len));
			}
			if(fall&&PP[i][j]){//步行
				if(point[i][j]>it.ttime+len){
					Q.push(node(i,j,it.ttime+len,it.k));
				}
			}else{
				fall=0;
			}
		}
	}
	return -1;
}
int main(){
	int m,n,k;
	fin>>m>>n>>k;
	if(m==1&&n==1){
		fout<<0<<endl;
		return 0;
	}
	PP.resize(m);
	point.resize(m);
	for(int i=0;i!=m;++i){
		PP[i].resize(n);
		point[i].resize(n);
		for(int j=0;j!=n;++j){
			flag[i][j]=0;
			point[i][j]=IMAX;
			char e;
			fin>>e;
			if(e=='P'){
				PP[i][j]=1;
			}else{
				PP[i][j]=0;
			}
			//cout<<PP[i][j];
		}
		//cout<<endl;
	}
	int r;
	r=core(m,n,k);
	if(r==-1){
		fout<<"impossible"<<endl;
	}else{
		fout<<r<<endl;
	}
	//-------------------------*/
	#if defined wolf
	cout<<endl<<(double)clock()/CLOCKS_PER_SEC<<'s'<<endl;
	#endif
	return 0;
}
//Designed by wolf
//Tue Apr 21 2015