Japan Alumni Group Summer Camp 2013 Warming Up

Submission #106559

Source codeソースコード

//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

Task問題 E - Magic Doors
User nameユーザ名 sky58
Created time投稿日時
Language言語 C++ (GCC 4.4.7)
Status状態 AC
Score得点 100
Source lengthソースコード長 1906 Byte
File nameファイル名
Exec time実行時間 50 ms
Memory usageメモリ使用量 3124 KB

Test case

Set

Set name Score得点 / Max score Cases
All 100 / 100 1,10,11,12,13,14,15,16,17,18,19,2,20,3,4,5,6,7,8,9

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
1 AC 46 ms 2976 KB
10 AC 29 ms 3000 KB
11 AC 47 ms 3124 KB
12 AC 50 ms 3092 KB
13 AC 27 ms 2996 KB
14 AC 28 ms 2996 KB
15 AC 27 ms 2992 KB
16 AC 31 ms 3052 KB
17 AC 32 ms 2996 KB
18 AC 31 ms 2984 KB
19 AC 48 ms 3124 KB
2 AC 34 ms 3040 KB
20 AC 28 ms 2996 KB
3 AC 33 ms 2972 KB
4 AC 28 ms 3040 KB
5 AC 30 ms 2984 KB
6 AC 27 ms 2996 KB
7 AC 30 ms 2920 KB
8 AC 34 ms 3048 KB
9 AC 32 ms 2984 KB