#define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include using namespace std; int map[102][102] = { 0, }; int map2[102][102] = { 0, }; int dirx[4] = { -1, 0, 1, 0 }; // 북동남서 int diry[4] = { 0, 1, 0 , -1 }; bool is_break(deque> qqq, int a, int b); //void Printsnake(FILE* fout, int N, int cur_dir, int cur_time, int a, int b, deque> ddd); //void Printapple(FILE* fout, int N); int main(void) { //FILE* fin = fopen("input.txt", "r"); //FILE* fout = fopen("output.txt", "w"); int N; // 맵 크기 int K; // 사과 개수 int x; int y; // 사과 위치 좌표 int L; // 명령 개수 int X; char C; // 명령 타입 int time = 0; //fscanf(fin, "%d", &N); scanf("%d", &N); if (N >= 2 && N <= 100) { //fscanf(fin, "%d", &K); scanf("%d", &K); if (K >= 0 && K <= 100) { for (int i = 0; i < K; i++) { // 맵 0으로 초기화, 사과는 1 //fscanf(fin, "%d %d", &x, &y); scanf("%d %d", &x, &y); map[x][y] = 1; } queue> q; // 명령 개수만큼 큐에 푸쉬 //fscanf(fin, "%d", &L); scanf("%d", &L); if (L >= 1 && L <= 100) { for (int i = 0; i < L; i++) { //fscanf(fin, "%d %c", &X, &C); scanf("%d %c", &X, &C); q.push(make_pair(X, C)); } /* 게임 시작 */ int cur_time = 0; // 게임 타임 체크 int cur_dir = 1; // 뱀 머리의 현재 방향 int a = 1; int b = 1; // 뱀 머리의 현재 좌표 deque> snake; // 뱀의 길이변화 추적을 위한 덱 // 사과 위치 출력 테스트 //Printapple(fout, N); while (!q.empty()) { // 큐에 명령있을 때 int next_time = q.front().first; char cmd = q.front().second; // 탐색 시작. 뱀은 처음 [1,1]에서 오른쪽(동쪽)방향으로 Go. while (next_time - cur_time != 0) { // 다음 명령이 떨어지는 시간까지 뱀이 해야할 일하도록 cur_time++; int next_x = a + dirx[cur_dir]; int next_y = b + diry[cur_dir]; //Printsnake(fout, N, cur_dir, cur_time, a, b, snake); if (next_x <= 0 || next_x > N || next_y <= 0 || next_y > N) { // 종료조건 1. 벽에 부딪히는 경우 time += cur_time; //fprintf(fout, "%d", time); printf("%d", time); return 0; } if (!snake.empty() && is_break(snake, next_x, next_y)) { // 종료조건 2. 자기 자신에게 부딪히는 경우 time += cur_time; //fprintf(fout, "%d", time); printf("%d", time); return 0; } snake.push_back(make_pair(a, b)); // 뱀 위치 기록을 위한 덱 if (map[next_x][next_y] != 1 && snake.size() > 1) { // 다음이동위치에 사과가 없는 상태에서 뱀의 사이즈가 2이상이면 snake.pop_front(); // 꼬리 당기기 } a = next_x; b = next_y; if (map[next_x][next_y] == 1) { // 다음이동위치에 사과가 있으면 사과먹고 갱신 map[next_x][next_y] = 0; } } if (cmd == 'L') { // 왼90도 턴 명령일때 if (cur_dir == 0) { cur_dir = 3; } else { cur_dir--; } } else if (cmd == 'D') { // 오90도 턴 명령일때 if (cur_dir == 3) { cur_dir = 0; } else { cur_dir++; } } q.pop(); } if (q.empty()) { // 더 이상 큐에 명령이 없을 때 그 방향 그대로 직진 cur_time++; int next_x = a + dirx[cur_dir]; int next_y = b + diry[cur_dir]; //Printsnake(fout, N, cur_dir, cur_time, a, b, snake); // 뱀 위치 출력을 위한 함수 if (next_x <= 0 || next_x > N || next_y <= 0 || next_y > N) { // 종료조건 1. 벽에 부딪히는 경우 time += cur_time; //fprintf(fout, "%d", time); printf("%d", time); return 0; } if (!snake.empty() && is_break(snake, next_x, next_y)) { // 종료조건 2. 자기 자신에게 부딪히는 경우 time += cur_time; //fprintf(fout, "%d", time); printf("%d", time); return 0; } snake.push_back(make_pair(a, b)); // 뱀 위치 기록을 위한 덱 if (map[next_x][next_y] != 1 && snake.size() > 1) { // 사과 없고 뱀 사이즈가 2 이상일 때 snake.pop_front(); // 사과가 없으면 꼬리 빼기 } a = next_x; b = next_y; if (map[next_x][next_y] == 1) { // 사과 먹으면 1 에서 0으로 map[next_x][next_y] = 0; } } //fprintf(fout, "%d", time); printf("%d", time); } } } return 0; } bool is_break(deque> qqq, int a, int b) { deque> new_q; new_q = qqq; for (int i = 0; i < new_q.size(); i++) { if (a == new_q.front().first && b == new_q.front().second) { return true; } new_q.pop_front(); } return false; }