[BOJ] 16957. 체스판 위의 공

BOJ/C++

[BOJ] 16957. 체스판 위의 공

IamToday 2020. 4. 25. 22:25

* 체스칸 위의 적힌 값은 변동이 없기 때문에 공의 위치에 따라 이동할 방향이 정해져있다.

* 이 특징을 이용해서, 좌표마다 움직이는 방향을 저장하고 (dir[][]) 해당 위치에 오면 저장된 방향으로 이동하도록 한다.

* 공을 이동시킬 때는 해당 좌표에 있는 공을 모두 가지고 이동한다.

#include <iostream>
#include <vector>
#include <queue>
#define INF 300001
using namespace std;
//BOJ https://www.acmicpc.net/problem/16957

int r, c;
int map[501][501];
int ball[501][501];
int dir[501][501];
bool visited[501][501];

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

typedef pair<int, int> pp;

void bfs()
{
    queue<pp> q;
    for (int i = 0; i < r; i++)
    {
        for (int j = 0; j < c; j++)
        {
            if (dir[i][j] == 4)
                continue;
            q.push(pp(i, j));
        }
    }

while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

if (dir[x][y] == 4 || ball[x][y] == 0)
            continue;

int cnt = ball[x][y];
        ball[x][y] = 0;

int nx = x + dx[dir[x][y]];
        int ny = y + dy[dir[x][y]];

ball[nx][ny] += cnt;
        q.push(pp(nx, ny));
    }
    for (int i = 0; i < r; i++)
    {
        for (int j = 0; j < c; j++)
        {
            cout << ball[i][j] << ' ';
        }
        cout << '\n';
    }
}
int main()
{

ios_base::sync_with_stdio(0);
    cin.tie(0);

cin >> r >> c;

for (int i = 0; i < r; i++)
    {
        for (int j = 0; j < c; j++)
        {
            cin >> map[i][j];
            ball[i][j] = 1;
        }
    }

for (int i = 0; i < r; i++)
    {
        for (int j = 0; j < c; j++)
        {
            int minn = map[i][j];
            int idx = 4;
            for (int d = 0; d < 9; d++)
            {
                int nx = i + dx[d];
                int ny = j + dy[d];

if (nx < 0 || nx >= r || ny < 0 || ny >= c)
                    continue;

if (minn > map[nx][ny])
                {
                    minn = map[nx][ny];
                    idx = d;
                }
            }

dir[i][j] = idx;
        }
    }

bfs();
    return 0;
}