提出 #70786449

---

ソースコード 拡げる

#include<bits/stdc++.h>
//bool Mst;
using namespace std;
using ll=long long;
using ld=long double;
//#define int ll
using pii=pair<int,int>;
const int inf=1e9;
pii sb[]={pii{0,1},pii{1,0},pii{0,-1},pii{-1,0}};
//bool Med;
signed main()
{
//	cerr<<"Memory Size: "<<abs((&Med)-(&Mst))/1024.0/1024<<" MB\n";
//	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//	freopen("in.in","r",stdin);
//	freopen("out.out","w",stdout);
	int t;cin>>t;
	while(t--) [&]()
	{
		int n,m;
		cin>>n>>m;
		vector<vector<array<int,4>>> dis(n,vector<array<int,4>>(m,{inf,inf,inf,inf}));
		struct node
		{
			int x,y,dir,d;
		};
		auto upd=[&](node nd)->int
		{
			auto [x,y,dir,d]=nd;
			if(dis[x][y][dir]>d) return dis[x][y][dir]=d,1;
			return 0;
		};
		deque<node> dq;
		vector<string> mp(n);
		for(int i=0;i<n;i++) cin>>mp[i];
		if(mp[0][0]=='A') dq.push_back({0,0,0,0});
		else if(mp[0][0]=='B') dq.push_back({0,0,1,0});
		else if(mp[0][0]=='C') dq.push_back({0,0,3,0});
		for(int dir:{0,1,2,3}) dq.push_back({0,0,dir,1});
		while(dq.size())
		{
			auto nd=dq.front();dq.pop_front();
			auto [x,y,dir,d]=nd;
			if(!upd(nd)) continue;
			int xx=x+sb[dir].first,yy=y+sb[dir].second;
			if(xx>=n||yy>=m||xx<0||yy<0) continue;
			if(mp[xx][yy]=='A') dq.push_front({xx,yy,dir,d});
			else if(mp[xx][yy]=='B') dq.push_front({xx,yy,dir^1,d});
			else if(mp[xx][yy]=='C') dq.push_front({xx,yy,3-dir,d});
			for(int dir:{0,1,2,3}) dq.push_back({xx,yy,dir,d+1});
		}
		cout<<dis[n-1][m-1][0]<<"\n";
	}();
	return 0;
}

提出情報

ジャッジ結果