[Algorithm][C++] JUNGOL 4193: swat. 애벌레 키우기1

url: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=3543 

JUNGOL

 

BOJ 뱀 문제와 거의 같은 문제. (https://hotamul.tistory.com/17)

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <deque>
using namespace std;

int N, M, D;
bool map[100][100];
bool body[100][100];
int DIR[10000];

const int dr[] = { -1,0,1,0 };
const int dc[] = { 0,1,0,-1 };

struct POS { int r, c; };
deque<POS> worm;

int solve() {
	int time = -1;
	int dir = 1;
	body[0][0] = true;
	worm.push_front({ 0,0 });
	while (1) {
		++time;
		if (DIR[time]) {
			dir = (dir + DIR[time]) % 4;
		}
		POS head = worm.front();
		int nr = head.r + dr[dir];
		int nc = head.c + dc[dir];
		if (nr < 0 || nr >= N || nc < 0 || nc >= N || body[nr][nc]) {
			break;
		}
		if (!map[nr][nc]) {
			POS tail = worm.back();
			body[tail.r][tail.c] = false;
			worm.pop_back();
		}
		else {
			map[nr][nc] = 0;
		}
		body[nr][nc] = true;
		worm.push_front({ nr,nc });
	}
	return time + 1;
}

int main() {
	scanf("%d %d", &N, &M);
	for (int i = 0; i < M; i++) {
		int r, c;
		scanf("%d %d", &r, &c);
		--r, --c;
		map[r][c] = true;
	}
	scanf("%d", &D);
	for (int i = 0; i < D; i++) {
		int t;
		char c;
		scanf("%d %c", &t, &c);
		if (c == 'R') {
			DIR[t] = 1;
		}
		else {
			DIR[t] = 3;
		}
	}
	int ret = solve();
	printf("%d", ret);
	return 0;
}