Submission #6437139

---

Source Code Expand

#include <bits/stdc++.h>
 
using namespace std;
 
#define lli long long int
#define REP(i,s,l) for(lli i=s;i<l;i++)
#define DEBUG 0
#define INF (1LL<<50)
#define MOD 1000000007


lli data[1100][1100]={-1};
lli flag[1100][1100]={-1};

signed main(){

	lli n,m,k;
	cin>>n>>m>>k;

	string d;
	cin>>d;

	/*普通に幅優先探索して、経路の復元を行う*/
	/*その時の経路復元したものを見て、かかる歩数をカウントすることにする*/

	pair<lli,lli> s;
	pair<lli,lli> g;

	REP(i,0,1100)REP(j,0,1100){
		data[i][j]=-1;
		flag[i][j]=-1;
	}

	REP(i,1,n+1)REP(j,1,m+1){
		char tmp;
		cin>>tmp;
		flag[i][j]=0;
		if(tmp=='.')data[i][j]=0;
		else if(tmp=='S'){
			s.first=j;
			s.second=i;
		}
		else if(tmp=='G'){
			g.first=j;
			g.second=i;
		}
		else{
			flag[i][j]=-1;
		}
	}

	queue<pair<lli,lli>> q;
	queue<string> qs;
	q.push(s);
	qs.push("");

	lli bflag=0;
	queue<string> qg;
	while(q.size()){
		pair<lli,lli> top = q.front();
		if(top.first == g.first && top.second == g.second){
			qg.push(qs.front());
		}
		string topS = qs.front();
		flag[top.second][top.first]=1;
		q.pop();
		qs.pop();

		lli dx[4]={-1,0,1,0};
		lli dy[4]={0,1,0,-1};
		string ds[4]={"L","D","R","U"};

		for(lli i=0;i<4;i++){
			lli nextX = top.first+dx[i];
			lli nextY = top.second+dy[i];

			if(flag[nextY][nextX]==0){
				q.push(make_pair(nextX,nextY));
				qs.push(topS+ds[i]);
			}
		}
	}

	if(qg.size()==0){
		cout<<-1<<endl;
		return 0;
	}

	string ans=qs.front();
	if(DEBUG)cout<<ans<<endl;

	lli cnt=0;
	lli nowIndex=0;
	lli last=INF;
	while(qg.size()){
		string ans=qg.front();
		qg.pop();

		if(DEBUG)cout<<ans<<endl;

		lli cnt=0;
		lli nowIndex=0;


		for(lli i=0;i<ans.size();i++){
			char nowC = ans.at(i);
	
			lli breakCnt=0;
			while(1){
				if(d.at(nowIndex)==nowC)break;
				nowIndex++;
				nowIndex%=d.size();
				breakCnt++;
				if(breakCnt >= k+10){
					cout<<-1<<endl;
					return 0;
				}
			}
			if(DEBUG)cout<<"nowIndex="<<nowIndex<<" breakCnt="<<breakCnt<<endl;
			cnt += breakCnt+1;
			if(DEBUG)cout<<"cnt="<<cnt<<endl;
			nowIndex++;
			nowIndex%=d.size();
		}
		last=min(last,cnt);
	//cout<<cnt<<endl;
	}
	cout<<last<<endl;

	return 0;
}

Submission Info

Judge Result