標準3190:Bam(アルゴリズムc++解答)

https://www.acmicpc.net/problem/3190
質問する
「Dummy」というドスゲームがありました.このゲームには蛇が這い出していて、りんごを食べると蛇の長さが増えます.ヘビが這い回って、壁や自分の体にぶつかって、ゲームは終わりました.
ゲームはNxN正方形の碁盤で行われ、一部の格にはりんごが置かれている.板の上下左右端に壁があります.ゲーム開始時、ヘビは一番上の一番左側にあり、ヘビの長さは1です.蛇は最初は右です.
ヘビは毎秒移動し、次のルールに従います.

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

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

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

リンゴの位置と蛇の移動経路を与えると,このゲームは数秒で終了する.
入力
最初の行は、プレートのサイズNを与える.(2 ≤ N ≤ 100)
次の行はりんごの個数Kを与えます.(0 ≤ K ≤ 100)
次のK行はリンゴの位置を示し,1番目の整数は行を表し,2番目の整数は列の位置を表す.りんごの位置が違います.一番上の左側(1行1列、起点)にはりんごがありません.
次の行は蛇の方向転換回数Lを与える.(1 ≤ L ≤ 100)
次のL行は蛇の方向変換情報を与え、整数Xと文字Cで構成され、ゲーム開始時間からX秒終了後に左(Cは「L」)または右(Cは「D」)に90度回転することを意味する.Xは10000以下の正の整数であり、方向変換情報はXが増加する順に与えられる.
に答える

具体的には尻尾が長くなります.

りんごのしっぽをそのまま食べて、頭+1
りんごを食べないとしっぽ-1、頭+1

すべてのヘッダーを管理→Dequeを書く!

📍 Queue, Deque
Queue

FIFO

back挿入をpush、front削除をpop

Deque

両端を挿入および削除可能

queueとstackの組み合わせ

📍 に答える

2 DアレイMAPで移動

りんご入りブロック1個、空きブロック0個

ヘビを含むブロックを2

にする

ホームポジションMAP[0][0]

1秒所定の方向に情報ヘッダを変換する+1

りんごの有無により、しっぽ-0 or-1

終了条件

胴体に頭部が当たる

壁に頭が当たる

1秒注意事項

退出条件→退出

次の乗り換えの街にはりんごはありませんか?
→次はヘッダとなるブロック=2、現在末尾=0

頭研いだ次のりんごはありますか?
→次はヘッダとなるブロック=2

変換方向が→変換方向であるかどうか

📍 コード#コード#

#include <iostream>
#include <deque>
#include <vector>

#define endl "\n"
#define MAX 100
using namespace std;

int N, K, L;
int MAP[MAX][MAX];

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

vector<pair<int, char>> change_dir; // 방향 변환 정보

void Input() {
	// 보드 크기 N
	cin >> N;

	// 사과 갯수 K
	cin >> K;
	
	// 사과의 위치들 (행, 열)
	for (int i = 0; i < K; i++) {
		int x, y;
		cin >> x >> y;
		x--, y--;
		MAP[x][y] = 1;
	}

	// 방향 변환 횟수 L
	cin >> L;

	// 방향 변환 정보 (X초 후에, D방향으로)
	for (int i = 0; i < L; i++) {
		int X;
		char D;
		cin >> X >> D;
		change_dir.push_back(make_pair(X, D));
	}
}

int Change_Dir(int d, char c) {
	// d: 현재 머리 방향 
	// c: L이면 왼쪽, D면 오른쪽으로 90도 회전
	// 0=위, 1=아래, 2=오른쪽, 3=왼쪽
	if (c == 'L') {
		if (d == 0) return 3;
		else if (d == 1) return 2;
		else if (d == 2) return 0;
		else if (d == 3) return 1;
	}
	
	else if (c == 'D') {
		if (d == 0) return 2;
		else if (d == 1) return 3;
		else if (d == 2) return 1;
		else if (d == 3) return 0;
	}
}

void PlayGame() {
	deque<pair<int, int>> Snake; //(x좌표, y좌표)
	int x = 0, y = 0, d = 0; // 시작위치 (0,0), 시작방향 오른쪽
	int Time = 0;
	int Idx = 0;
	Snake.push_back(make_pair(x, y));
	MAP[x][y] = 2;

	while (1) {
		Time++;

		int next_x = x + dx[d];
		int next_y = y + dy[d];

		// 1. 종료조건 (머리가 몸이랑 닿거나, 머리가 벽에 닿거나)
		if ((MAP[next_x][next_y] == 2 || next_x < 0 || next_y < 0 || next_x >= N || next_y >= N)) {
			break;
		}

		// 2. 머리가 갈 다음 블록에 사과가 없나 
		else if (MAP[next_x][next_y] == 0) {
			// 맵에 표시
			MAP[next_x][next_y] = 2;
			MAP[Snake.back().first][Snake.back().second] = 0;
			
			// 뱀 관리
			Snake.push_front(make_pair(next_x, next_y));
			Snake.pop_back();
		}

		// 3. 머리가 갈 다음 블록에 사과가 있나
		else if (MAP[next_x][next_y] == 1) {
			// 맵에 표시
			MAP[next_x][next_y] = 2;

			// 뱀 관리
			Snake.push_front(make_pair(next_x, next_y));
		}

		// 4. 방향 전환을 할 때인가 → 방향전환
		if (Idx < change_dir.size()) {
			if (Time == change_dir[Idx].first) {
				d = Change_Dir(d, change_dir[Idx].second);
				Idx++;
			}
		}

		x = next_x;
		y = next_y;
	}

	cout << Time << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	Input();
	PlayGame();

	return 0;
}