백준 16957번 체스판 위의 공 C++

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

16957번: 체스판 위의 공

 

이미 지나간 길은 따로 저장해서 불필요한 계산은 줄이는 메모이제이션 기법을 활용하여 문제를 해결하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

int dRow[8] = { -1,-1,0,1,1,1,0,-1 };
int dCol[8] = { 0,1,1,1,0,-1,-1,-1 };

int r, c;
vector<vector<int>> board;
vector<vector<int>> directions;
vector<vector<int>> ans;
vector<vector<pair<int,int>>> dests;

vector<pair<int, int>> poses;

void SetDirs(int row, int col) {
    int dir = -1;
    int val = board[row][col];
    for (int i = 0; i < 8; i++) {
        int nextRow = row + dRow[i];
        int nextCol = col + dCol[i];
        if (nextRow < 0 || nextRow >= r) continue;
        if (nextCol < 0 || nextCol >= c) continue;
        if (val < board[nextRow][nextCol]) continue;
        val = board[nextRow][nextCol];
        dir = i;
    }
    directions[row][col] = dir;
}

void dfs(int row, int col, int cnt) {
    if (dests[row][col].first != -1) {
        int destRow = dests[row][col].first;
        int destCol = dests[row][col].second;
        for (auto a : poses) {
            dests[a.first][a.second] = { destRow,destCol };
        }
        poses.clear();
        ans[destRow][destCol] += cnt;
        return;
    }
    poses.push_back({ row,col });
    int dir = directions[row][col];
    if (dir == -1) {
        for (auto a : poses) {
            dests[a.first][a.second] = { row,col };
        }
        poses.clear();
        ans[row][col] += cnt + 1;
    }
    else {
        int nextRow = row + dRow[dir];
        int nextCol = col + dCol[dir];
        dfs(nextRow, nextCol, cnt + 1);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> r >> c;
    board = vector<vector<int>>(r, vector<int>(c));
    directions = vector<vector<int>>(r, vector<int>(c));
    ans = vector<vector<int>>(r, vector<int>(c, 0));
    dests = vector<vector<pair<int, int>>>(r, vector<pair<int, int>>(c, { -1,-1 }));
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> board[i][j];
        }
    }
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            SetDirs(i, j);
        }
    }
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            dfs(i, j, 0);
        }
    }
    for (auto a : ans) {
        for (auto b : a) {
            cout << b << " ";
        }
        cout << "\n";
    }
}