백준 17822번 원판 돌리기 C++

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

17822번: 원판 돌리기

 

직접 돌리지는 않고 offset을 이용해서 현재 원판의 위치를 찾는식으로 문제를 해결하였다.

변수 하나를 실수로 잘못써서 시간을 좀 많이 썼다..

 

#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 n, m, t;

int dN[4] = { -1,1,0,0 };
int dM[4] = { 0,0,1,-1 };

vector<int> offsets;
vector<vector<float>> board;
vector<vector<bool>> erased;

bool isErase = false;

void Bfs(int _n, int _m) {

	float val = board[_n][_m];
	int sameCnt = 0;
	for (int i = 0; i < 4; i++) {
		int nextN = _n + dN[i];
		int nextM = _m + dM[i];
		if (nextN <= 0 || nextN > n) continue;
		if (nextN != _n) {
			nextM = nextM - offsets[_n] + offsets[nextN];
		}
		nextM = (nextM + m) % m;
		if (erased[nextN][nextM]) continue;
		if (val != board[nextN][nextM]) continue;
		sameCnt++;
	}
	if (sameCnt == 0) return;
	isErase = true;
	queue<pair<int, int>> q;
	q.push({ _n,_m });
	erased[_n][_m] = true;
	while (!q.empty()) {
		auto curr = q.front();
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nextN = curr.first + dN[i];
			int nextM = curr.second + dM[i];
			if (nextN <= 0 || nextN > n) continue;
			if (nextN != curr.first) nextM = nextM - offsets[curr.first] + offsets[nextN];
			nextM = (nextM + m) % m;
			if (erased[nextN][nextM]) continue;
			if (val != board[nextN][nextM]) continue;
			erased[nextN][nextM] = true;
			q.push({ nextN,nextM });
		}
	}
}

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

	cin >> n >> m >> t;
	offsets = vector<int>(n + 1, 0);
	board = vector<vector<float>>(n + 1, vector<float>(m));
	erased = vector<vector<bool>>(n + 1, vector<bool>(m, false));
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> board[i][j];
		}
	}
	for (int i = 0; i < t; i++) {
		int x, d, k;
		cin >> x >> d >> k;
		int offset;
		if (d == 0) offset = -k;
		else offset = k;
		for (int j = x; j <= n; j += x) {
			offsets[j] += offset;
			offsets[j] = (offsets[j] + m) % m;
		}
		for (int j = 1; j <= n; j++) {
			for (int k = 0; k < m; k++) {
				int currIdx = (k + offsets[j]) % m;
				if (erased[j][currIdx]) continue;
				Bfs(j, currIdx);
			}
		}

		if (isErase == false) {
			float sum = 0;
			float avr;
			int cnt = 0;
			for (int j = 1; j <= n; j++) {
				for (int k = 0; k < m; k++) {
					if (erased[j][k]) continue;
					cnt++;
					sum += board[j][k];
				}
			}
			if (cnt != 0) {
				avr = sum / cnt;
				for (int j = 1; j <= n; j++) {
					for (int k = 0; k < m; k++) {
						if (erased[j][k]) continue;
						if (board[j][k] > avr) board[j][k] -= 1.f;
						else if (board[j][k] < avr) board[j][k] += 1.f;
					}
				}
			}
		}

		isErase = false;
	}
	double ans = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < m; j++) {
			if (erased[i][j]) continue;
			ans += board[i][j];
		}
	}
	cout << int(ans);
}