Submission #106559

---

Source Code Expand

//JAG夏合宿13Day2E MagicDoors
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
typedef pair<int,pint> tint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
int dp[32][32][260],d2[32][32][260];
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
string ma[32];
priority_queue <tint> q;
int n,m,inf=1000000000;
void aedge(int t,int x,int y,int p){
	if(dp[x][y][p]<=t) return;
	dp[x][y][p]=t;q.push(mp(-t,mp(x*m+y,p)));
	return;
}
int main()
{
	cin>>n>>m;rep(i,n) cin>>ma[i];
	rep(i,32) rep(j,32) rep(k,260) dp[i][j][k]=d2[i][j][k]=inf;
	rep(i,n) rep(j,m){
		if(ma[i][j]=='^') aedge(0,i,j,0);
	}
	while(q.size()>0){
		tint r=q.top();q.pop();
		int t=-r.fi,x=r.se.fi/m,y=r.se.fi%m,p=r.se.se;
		if(d2[x][y][p]<=t) continue;d2[x][y][p]=t;
		//cout<<t<<' '<<x<<' '<<y<<' '<<p<<endl;
		char c=ma[x][y];
		if(c=='$'){
			cout<<t<<endl;return 0;
		}
		if(c<='h' && c>='a'){
			aedge(t+1+__builtin_popcount(p),x,y,p|(1<<(c-'a')));
		}
		if(c<='H' && c>='A'){
			aedge(t,x,y,(p|(1<<(c-'A')))-(1<<(c-'A')));
		}
		rep(i,4){
			int nx=x+dx[i],ny=y+dy[i];
			if(nx<0 || ny<0 || nx>=n || ny>=m) continue;
			char d=ma[nx][ny];
			if(d=='#') continue;
			if(d<='H' && d>='A'){
				if(!(p&(1<<(d-'A')))) continue;
			}
			aedge(t+1+__builtin_popcount(p),nx,ny,p);
		}
	}
	cout<<-1<<endl;
}

Submission Info

Judge Result