[白俊3190]蛇

問題の概要(意訳)

2 Dアレイ内のヘビの移動をシミュレート!
蛇には方向がある.方向命令は移動秒数後に受信する(意訳)
ゲーム開始時、ヘビは一番上の一番左側にあり、ヘビの長さは1です.蛇は最初は右です.
ヘビが這い回って、壁や自分の体にぶつかって、ゲームは終わりました.
ヘビは毎秒移動し、次のルールに従います.

まず、ヘビは体長を増やし、頭を次の格子に置く.

移動した格子にリンゴがあれば、格子のリンゴは消え、尻尾も動かない.

移動する格子にリンゴがなければ、体長を短くして尻尾のある格子を出すことができます.つまり、身長は変わらない.

入力

2 DフラットマップのサイズN,アップルの個数K

K行におけるリンゴの位置i,j

方向切替コマンドの数L

L行X秒後に適用される方向切替コマンド(時間順に進む)

しゅつりょく

ゲームは数秒後に終了します

アイデア

ルールを実施しながらシミュレーションを行っただけです.

紛らわしい場所

1.コマンドが入った時点

(0秒)---移動---1秒終了前に指向コマンドを実行(1秒)
問題はゲーム開始時間X秒が終わった後、クマンドが入ってきたことです.
こうして実現した.

2.競合

実は私の錯覚?これは混同された部分のためです.私も不思議に思ったのですが、衝突と言えば壁に垂直な方向に止まると壁の真ん前に(…)と思った.壁と同じ方向に蛇が壁の鼻の前を流れて行くのは大丈夫です...ハハハハ...遠くの蛇が移動方向に衝撃波を発射していると勘違いしているようです;;
私に似たような錯覚をする人はいませんが...

3.尻尾が小さくなった後の衝突検査vs尻尾が短くなる前の衝突検査

もちろん後者です.髪を一段前にする->りんご検査->りんごがないと少なくなります
りんごをチェックする過程で、尻尾との衝突も正しいと思います.
電子で表現するとき、問題の第三題で間違っています.

すくい取る

りんごを食べると、りんごは消えるはずですが、りんごがないと、体の縮小しか現れません.

ソースコード

#include<iostream>
#include<list>
#include<queue>
#include<memory.h>
using namespace std;

//뱀을 리스트로 표현 -> 사과먹을 때 / 못먹었을 때 추가가 용이하다
//움직일 때는 그냥 안에 내용물을 그대로 둬도 됨
struct pos {
	int i, j;
};
struct com {
	int x;
	char c;
};
int n;
bool tab[101][101];
int di[] = { -1,0,1,0 };
int dj[] = { 0,1,0,-1 };
int update_d(int d, char c) {
	if (c == 'L') {
		return ((d - 1) + 4) % 4;
	}
	else {
		return (d + 1) % 4;
	}
}
bool is_col_me(list<pos>& snake) {
	pos head = snake.front();

	for (list<pos>::iterator it = ++snake.begin(); it != snake.end(); it++) {
		if (it->i == head.i && it->j == head.j) {
			return true;
		}
	}
	return false;
}
bool is_col_wall(pos new_head) {
	if (new_head.i >= 1 && new_head.i <= n && new_head.j >= 1 && new_head.j <= n) {
		return false;
	}
	return true;
}
/*
void print_snake(list<pos>& snake, int d) {
	int marking[101][101];
	memset(marking, 0, sizeof(marking));
	cout << "dir : " << d << endl;
	int ctr = 1;
	for (list<pos>::iterator it = snake.begin(); it != snake.end(); it++) {
		cout << "(" << it->i << "," << it->j << ")\t";
		marking[it->i][it->j] = ctr++;
	}
	cout << endl << endl;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cout << marking[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl << endl << endl;
}
*/
int main() {
	int k;
	cin >> n>>k;
	memset(tab, 0, sizeof(tab));
	for (int ctr = 0; ctr < k; ctr++) {
		int i, j;
		cin >> i >> j;
		tab[i][j] = true;
	}
	int l;
	cin >> l;
	queue<com> commands;
	for (int i = 0; i < l; i++) {
		int x;
		char c;
		cin >> x >> c;
		commands.push(com{ x,c });
	}
	int time = 0;
	list<pos> snake;
	int d=1;//오른쪽
	snake.push_front(pos{ 1,1 });
	//cout << "처음 조건 : " << !is_col_me(snake) <<","<< !is_col_wall(snake.front()) <<","<< (time <= 10000) << endl;
	//시간이 다 되는 경우에 대해선 명시 안돼잇음
	while (true) {
		pos head = snake.front();
		pos new_head = pos{head.i+di[d],head.j+dj[d]};
		snake.push_front(new_head);
		//초가 지남
		time++;
		if (is_col_wall(snake.front()) || is_col_me(snake)) {
			break;
		}
		if (tab[new_head.i][new_head.j] == false) {//사과 없으면 줄어듦
			snake.pop_back();
		}
		else {//사과를 먹으면 없어지는 거 빠트림
			tab[new_head.i][new_head.j] = false;
		}
		
		//방향 커맨드를 받음
		if (!commands.empty()) {
			com cur = commands.front();
			if (cur.x == time) {
				commands.pop();
				d = update_d(d,cur.c);
			}
		}
		//cout << "cur time :" << time << endl;
		//print_snake(snake, d);

	}
	cout << time << endl;

}