Japan Alumni Group Summer Camp 2014 Day 4

Submission #232718

Source codeソースコード

#include <cstdio>
#include <cstdlib>
#include <cstring>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

int h,w;
char B[50][51];

int idx,ans;
char s[1001];

int x,y,dir;
bool vis[50][50][4][1001]; // [y][x][dir][idx]

void program();

void skip(){
	for(int c1=0,c2=0;s[idx];idx++){
		switch(s[idx]){
			case '[': c1++; break;
			case '{': c2++; break;
			case ']': c1--; if(c1<0) return; break;
			case '}': c2--; if(c2<0) return; break;
		}
	}
}

bool condition(){
	bool neg=false;
	if(s[idx]=='~') neg=true, idx++;
	switch(s[idx]){
		case 'N': idx++; return neg^(dir==1);
		case 'E': idx++; return neg^(dir==0);
		case 'S': idx++; return neg^(dir==3);
		case 'W': idx++; return neg^(dir==2);
		case 'C': idx++; return neg^(B[y+dy[dir]][x+dx[dir]]=='#');
		case 'T': idx++; return !neg;
	}
}

void sentence(){
	// if
	if(s[idx]=='['){
		idx++;
		if(condition()) program();
		else            skip();
		idx++;
	}
	// while
	else if(s[idx]=='{'){
		idx++;
		int idx0=idx;
		while(condition()){
			if(vis[y][x][dir][idx]) puts("-1"), exit(0);
			vis[y][x][dir][idx]=true;
			program();
			idx=idx0;
		}
		skip();
		idx++;
	}
	// move
	else{
		ans++;
		int dir2=(dir+2)%4;
		switch(s[idx]){
			case '^': if(B[y+dy[dir ]][x+dx[dir ]]!='#') y+=dy[dir ], x+=dx[dir ]; break;
			case 'v': if(B[y+dy[dir2]][x+dx[dir2]]!='#') y+=dy[dir2], x+=dx[dir2]; break;
			case '<': dir=(dir+1)%4; break;
			case '>': dir=(dir+3)%4; break;
		}
		if(B[y][x]=='g') printf("%d\n",ans), exit(0);
		idx++;
	}
}

void program(){
	while(s[idx] && strchr("[{^v<>",s[idx])) sentence();
}

int main(){
	scanf("%d%d",&h,&w);
	rep(i,h) scanf("%s",B[i]);
	scanf("%s",s);

	rep(i,h) rep(j,w) if(B[i][j]=='s') y=i, x=j, B[i][j]='.';
	dir=1;

	idx=ans=0;
	program();
	puts("-1");

	return 0;
}

Submission

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

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

./Main.cpp: In function ‘int main()’:
./Main.cpp:87: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./Main.cpp:88: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./Main.cpp:89: 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 00-sample1,00-sample2,00-sample3,01-corner-empty,01-corner-infinite-loop1,01-corner-infinite-loop2,01-corner-infinite-loop3,01-corner-infinite-loop4,02-large1,02-large2,02-large3,02-large4,02-large5,02-large6,03-misc1,03-misc2,04-maze-move-only-failure1,04-maze-move-only-failure10,04-maze-move-only-failure2,04-maze-move-only-failure3,04-maze-move-only-failure4,04-maze-move-only-failure5,04-maze-move-only-failure6,04-maze-move-only-failure7,04-maze-move-only-failure8,04-maze-move-only-failure9,04-maze-move-only-success1,04-maze-move-only-success10,04-maze-move-only-success2,04-maze-move-only-success3,04-maze-move-only-success4,04-maze-move-only-success5,04-maze-move-only-success6,04-maze-move-only-success7,04-maze-move-only-success8,04-maze-move-only-success9,04-maze-random-failure1,04-maze-random-failure10,04-maze-random-failure2,04-maze-random-failure3,04-maze-random-failure4,04-maze-random-failure5,04-maze-random-failure6,04-maze-random-failure7,04-maze-random-failure8,04-maze-random-failure9,04-maze-random-success1,04-maze-random-success10,04-maze-random-success2,04-maze-random-success3,04-maze-random-success4,04-maze-random-success5,04-maze-random-success6,04-maze-random-success7,04-maze-random-success8,04-maze-random-success9,04-maze-simple-failure1,04-maze-simple-failure10,04-maze-simple-failure2,04-maze-simple-failure3,04-maze-simple-failure4,04-maze-simple-failure5,04-maze-simple-failure6,04-maze-simple-failure7,04-maze-simple-failure8,04-maze-simple-failure9,04-maze-simple-success1,04-maze-simple-success10,04-maze-simple-success2,04-maze-simple-success3,04-maze-simple-success4,04-maze-simple-success5,04-maze-simple-success6,04-maze-simple-success7,04-maze-simple-success8,04-maze-simple-success9,05-nest1,05-nest2,06-long1

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00-sample1 AC 25 ms 796 KB
00-sample2 AC 25 ms 920 KB
00-sample3 AC 26 ms 736 KB
01-corner-empty AC 30 ms 676 KB
01-corner-infinite-loop1 AC 26 ms 840 KB
01-corner-infinite-loop2 AC 32 ms 748 KB
01-corner-infinite-loop3 AC 27 ms 800 KB
01-corner-infinite-loop4 AC 26 ms 668 KB
02-large1 AC 49 ms 7588 KB
02-large2 AC 57 ms 9896 KB
02-large3 AC 55 ms 9504 KB
02-large4 AC 57 ms 9504 KB
02-large5 AC 66 ms 9896 KB
02-large6 AC 80 ms 9892 KB
03-misc1 AC 24 ms 800 KB
03-misc2 AC 25 ms 804 KB
04-maze-move-only-failure1 AC 23 ms 924 KB
04-maze-move-only-failure10 AC 26 ms 736 KB
04-maze-move-only-failure2 AC 26 ms 924 KB
04-maze-move-only-failure3 AC 25 ms 916 KB
04-maze-move-only-failure4 AC 25 ms 796 KB
04-maze-move-only-failure5 AC 25 ms 928 KB
04-maze-move-only-failure6 AC 27 ms 804 KB
04-maze-move-only-failure7 AC 24 ms 796 KB
04-maze-move-only-failure8 AC 25 ms 800 KB
04-maze-move-only-failure9 AC 23 ms 924 KB
04-maze-move-only-success1 AC 24 ms 804 KB
04-maze-move-only-success10 AC 24 ms 924 KB
04-maze-move-only-success2 AC 24 ms 800 KB
04-maze-move-only-success3 AC 24 ms 924 KB
04-maze-move-only-success4 AC 29 ms 792 KB
04-maze-move-only-success5 AC 24 ms 672 KB
04-maze-move-only-success6 AC 25 ms 796 KB
04-maze-move-only-success7 AC 25 ms 924 KB
04-maze-move-only-success8 AC 25 ms 796 KB
04-maze-move-only-success9 AC 26 ms 796 KB
04-maze-random-failure1 AC 26 ms 796 KB
04-maze-random-failure10 AC 26 ms 928 KB
04-maze-random-failure2 AC 24 ms 924 KB
04-maze-random-failure3 AC 26 ms 800 KB
04-maze-random-failure4 AC 26 ms 804 KB
04-maze-random-failure5 AC 26 ms 708 KB
04-maze-random-failure6 AC 26 ms 816 KB
04-maze-random-failure7 AC 25 ms 920 KB
04-maze-random-failure8 AC 25 ms 796 KB
04-maze-random-failure9 AC 25 ms 800 KB
04-maze-random-success1 AC 25 ms 924 KB
04-maze-random-success10 AC 25 ms 924 KB
04-maze-random-success2 AC 23 ms 920 KB
04-maze-random-success3 AC 25 ms 796 KB
04-maze-random-success4 AC 25 ms 796 KB
04-maze-random-success5 AC 25 ms 800 KB
04-maze-random-success6 AC 24 ms 924 KB
04-maze-random-success7 AC 24 ms 804 KB
04-maze-random-success8 AC 25 ms 920 KB
04-maze-random-success9 AC 25 ms 920 KB
04-maze-simple-failure1 AC 24 ms 788 KB
04-maze-simple-failure10 AC 25 ms 916 KB
04-maze-simple-failure2 AC 26 ms 732 KB
04-maze-simple-failure3 AC 23 ms 792 KB
04-maze-simple-failure4 AC 26 ms 788 KB
04-maze-simple-failure5 AC 25 ms 796 KB
04-maze-simple-failure6 AC 24 ms 928 KB
04-maze-simple-failure7 AC 24 ms 808 KB
04-maze-simple-failure8 AC 26 ms 808 KB
04-maze-simple-failure9 AC 25 ms 928 KB
04-maze-simple-success1 AC 25 ms 796 KB
04-maze-simple-success10 AC 24 ms 924 KB
04-maze-simple-success2 AC 24 ms 924 KB
04-maze-simple-success3 AC 23 ms 928 KB
04-maze-simple-success4 AC 26 ms 928 KB
04-maze-simple-success5 AC 25 ms 784 KB
04-maze-simple-success6 AC 26 ms 796 KB
04-maze-simple-success7 AC 26 ms 808 KB
04-maze-simple-success8 AC 25 ms 796 KB
04-maze-simple-success9 AC 26 ms 916 KB
05-nest1 AC 26 ms 808 KB
05-nest2 AC 26 ms 808 KB
06-long1 AC 61 ms 4640 KB