AtCoder ABC #184 : E - Third Avenue

最近ABCが易化傾向？
https://atcoder.jp/contests/abc184/tasks/abc184_e

問題

グリッド上で、一部のマスに障害物とテレポーターがある。
テレポーターはいくつかグループになっている。
1手で以下のいずれかの移動ができるとき、スタートからゴールのセルへの最小移動手数を求めよ。

• 隣接マスへ移動する
• テレポーターのあるマスにいるとき、同じグループのテレポーターのあるマスに移動

解法

単なるBFS。
グループ毎にテレポーターが1回しか使わないようにしないとTLEするので注意。

int H,W;
string S[2020];
int D[2020][2020];
int SX,SY,GX,GY;
vector<pair<int,int>> C[26];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) {
		cin>>S[y];
		FOR(x,W) {
			D[y][x]=1<<30;
			if(S[y][x]=='S') SX=x,SY=y,S[y][x]='.';
			if(S[y][x]=='G') GX=x,GY=y,S[y][x]='.';
			if(S[y][x]>='a'&&S[y][x]<='z') C[S[y][x]-'a'].push_back({y,x});
		}
	}
	D[SY][SX]=0;
	queue<pair<int,int>> Q;
	Q.push({SY,SX});
	while(Q.size()) {
		auto p=Q.front();
		int cy=p.first;
		int cx=p.second;
		Q.pop();
		if(S[cy][cx]>='a'&&S[cy][cx]<='z') {
			FORR2(ty,tx,C[S[cy][cx]-'a']) {
				if(D[ty][tx]>D[cy][cx]+1) {
					D[ty][tx]=D[cy][cx]+1;
					Q.push({ty,tx});
				}
			}
			C[S[cy][cx]-'a'].clear();
		}
		
		FOR(i,4) {
			int d[4]={0,1,0,-1};
			int ty=cy+d[i];
			int tx=cx+d[i^1];
			if(tx<0||tx>=W||ty<0||ty>=H) continue;
			if(S[ty][tx]=='#') continue;
			if(D[ty][tx]>D[cy][cx]+1) {
				D[ty][tx]=D[cy][cx]+1;
				Q.push({ty,tx});
			}
		}
	}
	
	if(D[GY][GX]==1<<30) {
		cout<<-1<<endl;
	}
	else {
		cout<<D[GY][GX]<<endl;
	}
	
}

まとめ

やらかしてしまった。