白駿3190号蛇

質問する

https://www.acmicpc.net/problem/3190

コード#コード#

cpp

#include <string>
#include <vector>
#include<algorithm>
#include <iostream>
#include <queue>
using namespace std;

int N, K, L;

bool isRange(int y, int x) {
	if (0 <= y && y < N && 0 <= x && x < N) return true;
	else return false;
}

int main() {
	
	cin >> N >> K;

	vector<vector<int>> map(N, vector<int>(N, 0));
	map[0][0] = 1;
	for (int i = 0; i < K; i++) {
		int y, x;
		cin >> y >> x;
		map[y-1][x-1] = 2;
	}

	cin >> L;
	vector<pair<int, char>> move(L+1);
	for (int i = 0; i < L; i++) {
		cin >> move[i].first;
		cin >> move[i].second;
	}
	move[L] = { 100,'D' };
	int d = 0; //현재 나의 방향
	int dist[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };


	
	int time = 0;
	pair<int, int> head = { 0,0 };
	pair<int, int> tail = { 0,0 };

	queue<int> q;
	for (auto i : move) {
		while(time< i.first) {
			head.first += dist[d][0];
			head.second += dist[d][1];
			int headY = head.first;
			int headX = head.second;
			q.push(d);
			time++;
			if (!isRange(headY, headX)|| map[headY][headX] == 1) { //범위를 벋어나거나 자기 자신과 부딪히면 종료
				cout <<time;				
				exit(0);
			}			
			
			if (map[headY][headX] == 0) { //빈칸이라면 한칸 움직이고 tail의 인덱스를 변경	
				map[headY][headX] = 1;
				map[tail.first][tail.second] = 0;
				
				tail.first += dist[q.front()][0];
				tail.second += dist[q.front()][1];
				q.pop();
			}
			else if(map[headY][headX] == 2) map[headY][headX] = 1;
			/*for (auto i : map) {
				for (int j : i)
					cout << j << " ";
				cout << endl;
			}
			cout << time<<endl;*/
			
		}
		
		if (i.second == 'D') d++;
		else d--;

		if (d >= 4) d -= 4;
		if (d < 0)d += 4;
	}
	
}

python

import sys

N = int(sys.stdin.readline())
K = int(sys.stdin.readline())
maps = [[0 for _ in range(N)] for _ in range(N)]

for k in range(K):  # mark apple
    r, c = map(int, sys.stdin.readline().split())
    maps[r-1][c-1] = 2

L = int(sys.stdin.readline())
change = dict()
for l in range(L):
    t, d = sys.stdin.readline().split()
    change[int(t)] = d

maps[0][0] = 1
# R,D,L,U
dm = [(0, 1), (1, 0), (0, -1), (-1, 0)]

time = 0
x, y = 0, 0
move = 0
now = [(0, 0)]
while True:
    time += 1
    dy, dx = dm[move]
    nx, ny = x+dx, y+dy
    # on board
    if 0 <= nx < N and 0 <= ny < N:
        # find apple
        if maps[ny][nx] == 2:
            now.append((nx, ny))
            maps[ny][nx] = 1
        # blank
        elif maps[ny][nx] == 0:
            maps[ny][nx] = 1
            now.append((nx, ny))
            rx, ry = now[0]
            del now[0]
            maps[ry][rx] = 0
        # bump self
        elif maps[ny][nx] == 1:
            break
        x, y = nx, ny
        # time of change direction
        if time in change:
            if change[time] == 'L':
                move += -1
                if move >= 4:
                    move -= 4
                elif move < 0:
                    move += 4
            elif change[time] == 'D':
                move += 1
                if move >= 4:
                    move -= 4
                elif move < 0:
                    move += 4
    # out of board
    else:
        break
print(time)

に答える

まず,int 2次元配列を用いてマッピングを作成し,ヘビを表す1を0,0に保存した.
リンゴの位置値を受け入れて地図に保存し、ヘビの現在のhead座標値とtail座標値を変数として管理します.
headとtailインデックスを管理する際に注意したいのは、現在のheadの進行方向とtailの進行方向が異なる可能性があるため、キューを使用してhead移動時にキューに方向値を追加し、tail移動時にキューから値を減算して解くことです!