結果

問題 No.331 CodeRunnerでやれ
ユーザー koyumeishikoyumeishi
提出日時 2015-12-25 00:26:40
言語 C++11
(gcc 11.4.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,685 bytes
コンパイル時間 971 ms
コンパイル使用メモリ 112,760 KB
実行使用メモリ 84,152 KB
平均クエリ数 31.18
最終ジャッジ日時 2023-09-23 22:59:06
合計ジャッジ時間 8,756 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 130 ms
23,664 KB
testcase_01 AC 135 ms
23,652 KB
testcase_02 AC 157 ms
23,392 KB
testcase_03 AC 196 ms
23,548 KB
testcase_04 TLE -
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};

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

	// 0 ?
	// 1 visit
	// 2 wall
	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);
		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)%4]][y + dy[(dir+1)%4]];
	};
	auto check_left = [&](){
		return field[x + dx[(dir+1)%4]][y + dy[(dir+1)%4]];
	};

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

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

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

	};

	auto turn_left = [&](){
		puts("L");
		fflush(stdout);
		dir = (dir+3)%4;
		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) continue;
				//do something
				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)%4], y+dy[(dir+1)%4]}){
				turn_right();
				go_foward();
			}else if(p == pair<int,int>{x+dx[(dir+3)%4], y+dy[(dir+3)%4]}){
				turn_left();
				go_foward();
			}else if(p == pair<int,int>{x+dx[(dir+2)%4], y+dy[(dir+2)%4]}){
				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==-1) return 0;
		if(d==-2){
			go_foward();
			continue;
		}

		if(field[x][y] == 0){
			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){
					hoge[i] = {{x,y},dir};
					//st.push({{x,y},dir});
					//cerr << 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_();
		}

		//cerr << field << endl;
	}
	return 0;
}
0