結果

問題 No.331 CodeRunnerでやれ
ユーザー koyumeishikoyumeishi
提出日時 2015-12-25 00:51:44
言語 C++11
(gcc 11.4.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,925 bytes
コンパイル時間 1,313 ms
コンパイル使用メモリ 113,328 KB
実行使用メモリ 86,888 KB
最終ジャッジ日時 2024-07-16 22:45:15
合計ジャッジ時間 14,531 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <functional>
#include <set>
#include <ctime>
#include <stack>
#include <random>
using namespace std;
template<class T> istream& operator >> (istream& is, vector<T>& vec){for(T& val: vec) is >> val; return is;}
template<class T> istream& operator , (istream& is, T& val){ return is >> val;}
template<class T> ostream& operator << (ostream& os, vector<T>& vec){for(int i=0; i<vec.size(); i++) os << vec[i] << (i==vec.size()-1?"\n":" ");return os;}

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

#include <cassert>

int main(){
	char buff[100];
	int s = 0;

	int cnt = 0;

	// 0 ?
	// 1 visit
	// 2 wall
	// 3 space
	vector<vector<int>> field(50, vector<int>(50, 0));

	int x = 25;
	int y = 25;
	int dir = 0;

	auto update = [&](){
		string s(buff);
		if(s=="Merry Christmas!") return -1;
		if(s=="20151224") return -2;

		int d;
		sscanf(buff, "%d", &d);
		for(int k=1; k<=d; k++){
			if( !field[x + k*dx[dir]][y + k*dy[dir]] ) field[x + k*dx[dir]][y + k*dy[dir]] = 3;
		}
		field[x + (d+1)*dx[dir] ][ y + (d+1) * dy[dir] ] = 2;
		return d;
	};

	auto check_foward = [&](){
		return field[x + dx[dir] ][y + dy[dir]];
	};

	auto check_right = [&](){
		return field[x + dx[(dir+1)&3]][y + dy[(dir+1)&3]];
	};
	auto check_left = [&](){
		return field[x + dx[(dir+1)&3]][y + dy[(dir+1)&3]];
	};

	auto go_foward = [&](){
		if(field[x + dx[dir]][y + dy[dir]] == 2) return;
		puts("F");
		cnt++;
		fflush(stdout);
		x += dx[dir];
		y += dy[dir];
		gets(buff);
		update();
	};

	auto go_backward = [&](){
		if(field[x + dx[(dir+2)&3]][y + dy[(dir+2)&3]] == 2) return;
		puts("B");
		cnt++;
		fflush(stdout);
		x -= dx[dir];
		y -= dy[dir];
		gets(buff);
		update();
	};

	auto turn_right = [&](){
		puts("R");
		cnt++;
		fflush(stdout);
		dir = (dir+1)&3;
		gets(buff);
		update();

	};

	auto turn_left = [&](){
		puts("L");
		cnt++;
		fflush(stdout);
		dir = (dir+3)&3;
		gets(buff);
		update();
	};

	stack<pair<pair<int,int>,int>> st;

	auto move_ = [&](){
		vector<vector<pair<int,int>>> last(50, vector<pair<int,int>>(50, {-1,-1}));
		queue<pair<int,int>> q;
		q.push(st.top().first);

		while(q.size()){
			auto pos = q.front(); q.pop();
			if(pos == st.top().first) break;
			//cerr << pos.first << " " << pos.second << " " << dir;


			int x_ = pos.first;
			int y_ = pos.second;
			for(int k__=0; k__<4; k__++){
				int new_x = x_+ dx[k__];
				int new_y = y_ + dy[k__];
				if(field[new_x][new_y] == 1 || field[new_x][new_y] == 3){
					if(last[new_x][new_y] == last[0][0] ){
						last[new_x][new_y] = {x_,y_};
						q.push({x_,y_});
					}
				}
			}
		}
		while(pair<int,int>{x,y} != st.
			top().first){
			auto p = last[x][y];
			if(p == pair<int,int>{x+dx[(dir+1)&3], y+dy[(dir+1)&3]}){
				turn_right();
				go_foward();
			}else if(p == pair<int,int>{x+dx[(dir+3)&3], y+dy[(dir+3)&3]}){
				turn_left();
				go_foward();
			}else if(p == pair<int,int>{x+dx[(dir+2)&3], y+dy[(dir+2)&3]}){
				go_backward();
			}else{
				go_foward();
			}
		}

		while(pair<pair<int,int>,int>{{x,y},dir} != st.top()){
			turn_right();
		}
	};
/*
	gets(buff);
	while(true){
		int d = update();
		if(d<=0) break;
		go_foward();
	}
*/
	while(true){
		assert(cnt<=10000);

		int d = update();
		if(d==-1) return 0;
		if(d==-2){
			go_foward();
			continue;
		}

		if(field[x][y] == 0 || field[x][y] == 3){
			field[x][y] = 1;
			vector<pair<pair<int,int>,int>> hoge(5, {{-1,-1},-1});
			for(int i=0; i<4; i++){
				int z = check_foward();
				if(z==0 || z==3){
					hoge[i] = {{x,y},dir};
				}
				turn_right();
				update();
			}
			for(int i:{2,3,0,1}){
				if(hoge[i] == hoge[4]) continue;
				st.push(hoge[i]);
			}
		}

		if(st.top() == pair<pair<int,int>,int>{{x,y}, dir}){
			st.pop();
			go_foward();
			continue;
		}else{
			move_();
		}
	}
	return 0;
}
0