술래잡기

https://www.codetree.ai/training-field/frequent-problems/problems/hide-and-seek/description?page=1&pageSize=20

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

술래의 시야는 항상 3

 

술래의 위치는 행, 열 -> (n + 1) / 2

move_cnt는 1, 1, 2, 2, ...

마법사 상어와 토네이도와 다른 점은 이 문제는

끝에 닿으면 다시 돌아간다.

 

m명의 도망자가 먼저 동시에 움직인다

이동 도중 도망자들의 위치는 "겹칠 수 있음"에 유의합니다.

-> vector<int> map[104][104]

움직이려는 칸에 술래가 있는 경우라면 움직이지 않습니다.

 

<소스 코드>

#include <iostream>
#include <vector>
#include <cstring>
 
using namespace std;
 
int dist(int x1, int y1, int x2, int y2)
{
    return abs(x1 - x2) + abs(y1 - y2);
}
 
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };
 
int n, m, h, turn;
 
int len = 0, cnt = 0;
bool opposite = false;
int curlen = 1;
 
struct wichi {
    int x, y, dir;
};
 
struct info
{
    int row, col, p_dir;
    bool live;
};
 
wichi it;
 
vector<int> map[104][104];
bool tree_map[104][104];
 
vector<info> player;
 
void player_move()
{
    for (int i = 1; i <= m; i++)
    {
        if (player[i].live == false)
            continue;
        int x = player[i].row;
        int y = player[i].col;
        int dir = player[i].p_dir;
 
        if (dist(x, y, it.x, it.y) <= 3)
        {
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            if (nx < 1 || nx > n || ny < 1 || ny > n)
            {
                if (dir == 0)
                {
                    dir = 2;
                    player[i].p_dir = dir;
                }
                else if (dir == 1)
                {
                    dir = 3;
                    player[i].p_dir = dir;
                }
                else if (dir == 2)
                {
                    dir = 0;
                    player[i].p_dir = dir;
                }
                else if (dir == 3)
                {
                    dir = 1;
                    player[i].p_dir = dir;
                }
 
                nx = x + dx[dir];
                ny = y + dy[dir];
                if ((nx == it.x) && (ny == it.y))
                    continue;
                else {
                    player[i].row = nx;
                    player[i].col = ny;
                }
            }
            else
            {
                if ((nx == it.x) && (ny == it.y))
                    continue;
                else {
                    player[i].row = nx;
                    player[i].col = ny;
                }
            }
        }
 
    }
 
}
 
void sul_move()
{
    int x = it.x;
    int y = it.y;
    int dir = it.dir;
 
    int nx = x + dx[dir];
    int ny = y + dy[dir];
 
    len++;
 
    if (len == curlen)
    {
        len = 0;
        cnt++;
        if (opposite == false)
        {
            if (dir == 3)
                dir = 0;
            else dir++;
        }
        else
        {
            if (dir == 0)
                dir = 3;
            else dir--;
        }
        if (cnt == 2)
        {
            cnt = 0;
            if (opposite == false) curlen++;
            else curlen--;
        }
    }
 
    if (nx == 1 && ny == 1)
    {
        opposite = true;
        curlen = n - 1;
        dir = 2;
        // 3번 돌아야 함
        cnt = -1;
        len = 0;
    }
    else if (nx == (n + 1) / 2 && ny == (n + 1) / 2)
    {
        opposite = false;
        curlen = 1;
        dir = 0;
        cnt = 0;
        len = 0;
    }
    it = { nx,ny,dir };
}
 
void drawing()
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
            map[i][j].clear();
    }
 
    for (int i = 1; i <= m; i++)
    {
        if (!player[i].live)
            continue;
        map[player[i].row][player[i].col].push_back(i);
    }
}
 
int main()
{
    cin >> n >> m >> h >> turn;
 
    player.resize(m + 1);
    it.x = n / 2 + 1;
    it.y = n / 2 + 1;
    it.dir = 0;
 
    for (int i = 1; i <= m; i++)
    {
        int way;
        cin >> player[i].row >> player[i].col >> way;
        if (way == 1)
            player[i].p_dir = 1;
        else if (way == 2)
            player[i].p_dir = 2;
        player[i].live = true;
    }
 
    for (int i = 0; i < h; i++)
    {
        int r, c;
        cin >> r >> c;
        tree_map[r][c] = true;
    }
 
    int ans = 0;
 
    for (int t = 1; t <= turn; t++)
    {
        drawing();
        player_move();
        drawing();
 
        sul_move();
 
        int jab = 0;
 
        int sul_x = it.x;
        int sul_y = it.y;
        int sul_dir = it.dir;
 
        if (!tree_map[sul_x][sul_y])
        {
            for (int k = 0; k < map[sul_x][sul_y].size(); k++)
            {
                jab++;
                player[map[sul_x][sul_y][k]].live = false;
            }
        }
 
        for (int i = 0; i < 2; i++)
        {
            sul_x += dx[sul_dir];
            sul_y += dy[sul_dir];
 
            if (sul_x < 1 || sul_x > n || sul_y < 1 || sul_y > n)
                break;
 
            if (!tree_map[sul_x][sul_y])
            {
                for (int k = 0; k < map[sul_x][sul_y].size(); k++)
                {
                    jab++;
                    player[map[sul_x][sul_y][k]].live = false;
                }
            }
        }
 
        ans += (t * jab);
    }
 
    cout << ans << '\n';
}