Submission #6437212

---

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};

#define L 0
#define U 1
#define R 2
#define D 3

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;
	}

	map<char,vector<lli>> av;
	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;
		}
	}

	REP(i,0,d.size()){
		char nowC = d.at(i);
		av[nowC].push_back(i);
	}

	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);

			auto itr = lower_bound(av[nowC].begin(),av[nowC].end(),nowIndex);
			if(itr==av[nowC].end()){
				itr = av[nowC].begin();
				cnt += d.size() - nowIndex;
				nowIndex=0;
			}
			if(DEBUG)cout<<"*itr="<<*itr<<endl;
			cnt += (*itr) -nowIndex+1;
			nowIndex = *itr;
			nowIndex++;
			nowIndex %= d.size();
		}
		last=min(last,cnt);
	//cout<<cnt<<endl;
	}
	cout<<last<<endl;

	return 0;
}

Submission Info

Judge Result