Japan Alumni Group Summer Camp 2013 Warming Up

Submission #101929

Source codeソースコード

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;

struct state
{
	int x, y;
	int mask;
	int cost;

	state(int xa, int ya, int ma, int ca)
	{
		x = xa;
		y = ya;
		mask = ma;
		cost = ca;
	}

	state() {} 
};

inline bool operator<(const state& a, const state& b)
{
	return a.cost > b.cost;
}

int H, W;
char in[31][31];
int bitc[256];
int ax[4] = {-1, 0, 0, 1};
int ay[4] = {0, 1, -1, 0};

char at(int x, int y)
{
	if(x<0 || y<0 || x>=H || y>=W) return '#';
	return in[x][y];
}

bool vis[30][30][256];
int bx, by, ex, ey;

int main()
{
	for(int i=0;i<256;i++){

		bitc[i] = 0;
		for(int j=0;j<8;j++) if(i&(1<<j)) ++bitc[i];
	}

	scanf("%d%d", &H, &W);
	for(int i=0;i<H;i++){
		scanf("%s", in[i]);
		for(int j=0;j<W;j++){
			if(in[i][j]=='^'){
				bx = i; by = j; in[i][j]='.';
			}else if(in[i][j]=='$'){
				ex = i; ey = j; in[i][j]='.';
			}
		}
	}

	priority_queue<state> Q;
	state tmp;
	
	for(int i=0;i<H;i++) for(int j=0;j<W;j++)
		for(int k=0;k<256;k++) vis[i][j][k] = false;
	Q.push(state(bx, by, 0, 0));

	while(!Q.empty()){
		tmp = Q.top(); Q.pop();
		if(vis[tmp.x][tmp.y][tmp.mask]) continue;
		vis[tmp.x][tmp.y][tmp.mask] = true;
		//printf("%d %d %d: %d\n", tmp.x, tmp.y, tmp.mask, tmp.cost);
		if(tmp.x == ex && tmp.y == ey){
			printf("%d\n", tmp.cost);
			return 0;
		}

		char iv = in[tmp.x][tmp.y];
		if(iv >= 'a' && iv <= 'z'){
			if(!(tmp.mask & (1<<(iv-'a')))){
				//enable
				Q.push(state(tmp.x, tmp.y, tmp.mask | (1<<(iv-'a')), tmp.cost + 1 + bitc[tmp.mask]));
			}
		}
		if(iv >= 'A' && iv <= 'Z'){
			if((tmp.mask & (1<<(iv-'A')))){
				//disable
				Q.push(state(tmp.x, tmp.y, tmp.mask ^ (1<<(iv-'a')), tmp.cost + 0));
			}
		}

		for(int i=0;i<4;i++){
			int x2=ax[i]+tmp.x, y2=ay[i]+tmp.y;
			if(at(x2, y2) == '#') continue;

			iv = in[x2][y2];
			if(iv >= 'A' && iv <= 'Z'){
				if(!(tmp.mask & (1<<(iv-'A')))) continue;
			}

			Q.push(state(x2, y2, tmp.mask, tmp.cost + 1 + bitc[tmp.mask]));
		}
	}

	puts("-1");
	return 0;
}

Submission

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

Compiler messageコンパイルメッセージ

./Main.cpp: In function ‘int main()’:
./Main.cpp:51: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./Main.cpp:53: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result

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 21 ms 800 KB
10 AC 22 ms 920 KB
11 AC 51 ms 1320 KB
12 AC 40 ms 932 KB
13 AC 20 ms 804 KB
14 AC 21 ms 796 KB
15 AC 24 ms 756 KB
16 AC 22 ms 1056 KB
17 AC 24 ms 992 KB
18 AC 83 ms 996 KB
19 AC 35 ms 1316 KB
2 AC 20 ms 796 KB
20 AC 23 ms 928 KB
3 AC 20 ms 804 KB
4 AC 22 ms 932 KB
5 AC 21 ms 736 KB
6 AC 20 ms 924 KB
7 AC 20 ms 800 KB
8 AC 22 ms 932 KB
9 AC 20 ms 844 KB