結果

問題 No.331 CodeRunnerでやれ
ユーザー naimonon77naimonon77
提出日時 2016-10-09 21:40:16
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 360 ms / 5,000 ms
コード長 4,347 bytes
コンパイル時間 2,170 ms
コンパイル使用メモリ 178,732 KB
実行使用メモリ 32,352 KB
平均クエリ数 274.59
最終ジャッジ日時 2024-07-17 00:28:51
合計ジャッジ時間 8,257 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 171 ms
25,488 KB
testcase_01 AC 164 ms
24,848 KB
testcase_02 AC 216 ms
25,232 KB
testcase_03 AC 180 ms
24,836 KB
testcase_04 AC 196 ms
24,580 KB
testcase_05 AC 204 ms
25,220 KB
testcase_06 AC 216 ms
24,976 KB
testcase_07 AC 268 ms
25,220 KB
testcase_08 AC 295 ms
24,592 KB
testcase_09 AC 302 ms
25,220 KB
testcase_10 AC 262 ms
25,208 KB
testcase_11 AC 262 ms
25,824 KB
testcase_12 AC 300 ms
25,220 KB
testcase_13 AC 276 ms
24,836 KB
testcase_14 AC 360 ms
32,352 KB
testcase_15 AC 320 ms
24,836 KB
testcase_16 AC 311 ms
24,836 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES

#include "bits/stdc++.h"
#define REP(i,a,b) for(int i=a;i<b;++i)
#define rep(i,n) REP(i,0,n)
#define ll long long
#define ull unsigned ll
typedef long double ld;
#define ALL(a) begin(a),end(a)
#define ifnot(a) if(not (a))
#define dump(x)  cerr << #x << " = " << (x) << endl
using namespace std;

// #define int ll
#ifdef _MSC_VER
const bool test = true;
#else 
const bool test = false;
#endif

int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };
#define INF (1 << 28)
ull mod = (int)1e9 + 7;
//.....................
#define MAX (int)1e5 + 5

#define SIZE 50

enum Dir {
	up, r, down, l
};

void draw_map(char map[][SIZE], int a, int x, int y, int dir) {
	int i;
	for (i = 1; i < a + 1; i++) {
		switch (dir) {
		case  up: y += 1; break;
		case down: y -= 1; break;
		case   r: x += 1; break;
		case   l: x -= 1; break;
		}
		map[x][y] = '.';
	}
	switch (dir) {
	case  up: y += 1; break;
	case down: y -= 1; break;
	case   r: x += 1; break;
	case   l: x -= 1; break;
	}
	map[x][y] = '#';
	// map[x][y] = '!';
}

void print_map(char map[][SIZE]) {
	int i, j;
	for (i = SIZE - 1; i>-1; i--) {
		for (j = 0; j<SIZE; j++) {
			if (map[j][i] == 0) printf(" ");
			else printf("%c", map[j][i]);
		}
		puts("");
	}
}

struct Route1 {
	vector<int> route;
	bool visited[SIZE][SIZE];
	int x, y;
	int index;
	Route1() {
		int i, j;
		rep(i, SIZE) {
			rep(j, SIZE) visited[i][j] = false;
		}
	}
};


char muki_convert(int dir) {
	char c;
	switch (dir) {
	case  up: c = '^'; break;
	case down: c = 'v'; break;
	case  r: c = '>'; break;
	case  l: c = '<'; break;
	default: assert(false); 
	}
	return c;
}


void chackq(Route1 route1) {
	int i;
	rep(i, route1.route.size()) {
		cout << muki_convert(route1.route[i]);
	}
	puts("");
}

bool map_search(char map[][SIZE],
	int x, int y, queue<Route1>& q, const Route1& now)
{
	if ((not now.visited[x][y]) && map[x][y] != '#') {
		Route1 next = now;
		next.x = x, next.y = y;
		next.visited[x][y] = true;
		q.push(next);
		return true;
	}
	return false;
}

// 最も近い分からない場所を探索
// 最後は行けるか分からない
Route1 wfs(char map[][SIZE], int x, int y) {
	queue< Route1 > q;
	Route1 now;
	now.x = x; now.y = y;
	now.index = 0;
	now.visited[x][y] = true;
	q.push(now);
	while (q.size()) {
		now = q.front(); q.pop();
		int x = now.x, y = now.y;
		if (test) printf("map[%d][%d] = %c", x, y, map[x][y]);
		if (test) puts("");
		if (map[x][y] == 0) {
			return now;
		}
		rep(i, 4) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (map_search(map, nx, ny, q, now)) {
				q.back().route.push_back(i);
				if (test) chackq(q.front());
			}
		}
	}
	exit(1);
}

void player_move(int dir, int& x, int& y,
	char map[][SIZE])
{
	map[x][y] = '.';
	switch (dir) {
	case  up: y++; map[x][y] = '^'; break;
	case down: y--; map[x][y] = 'v'; break;
	case  r: x++; map[x][y] = '>'; break;
	case  l: x--; map[x][y] = '<'; break;
	}
}

void muki_draw(int dir, int& x, int& y,
	char map[][SIZE])
{
	switch (dir) {
	case  up: map[x][y] = '^'; break;
	case down: map[x][y] = 'v'; break;
	case  r: map[x][y] = '>'; break;
	case  l: map[x][y] = '<'; break;
	}
}

int main() {
	/*
	cin.tie(0);
	ios::sync_with_stdio(false);
	*/
	char map[SIZE][SIZE] = { 0 };  // 0 or '.' or '#'
	int x = SIZE / 2, y = SIZE / 2;
	int dir = down;
	string s;
	Route1 route1;
	route1.index = 0;
	muki_draw(dir, x, y, map);
	if (test) print_map(map);
	while (cin >> s) {
		char c;
		if (s == "Merry") break;
		int a = stoi(s);
		if (a > 50) {
			c = 'F';
			player_move(dir, x, y, map);
		}
		else {
			draw_map(map, a, x, y, dir);
			int& index = route1.index;
			if (a == 0 or route1.route.size() == index) {
				route1 = wfs(map, x, y);
				if (test) {
					int i;
					REP(i, index, route1.route.size()) {
						cout << muki_convert(route1.route[i]);
					}
					puts("");
				}
			}
			if (a != 0 && route1.route[index] == dir) {
				player_move(dir, x, y, map);
				c = 'F';
				index++;
			}
			else {
				int next_dir = route1.route[index];
				dump(dir);
				dump(next_dir);
				if ((dir - next_dir + 4) % 4 < 3) {
					c = 'L';
					dir--;
					if (dir < up) dir = l;
				}
				else {
					c = 'R';
					dir++;
					if (dir > l) dir = 0;
				}
				muki_draw(dir, x, y, map);
			}
		}
		if (test) print_map(map);
		cout << c << endl;
	}
	cin >> s;
	return 0;
}
0