[백준] 마법사 상어와 비바라기

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

21610번: 마법사 상어와 비바라기

 

구현에 어렵지 않은 문제였다.

memset 사용을 위해서는 include <cstring> 잊지 말자.

vector의 erase 함수는 size를 0으로 만드는 기능을 한다.

#define _CRT_SECURE_NO_DEPRECATE

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;

int N, M;
int map[51][51];
bool visited[51][51];
vector<vector<int>> movement;
vector< pair<int, int> > cloud;

int dr[9] = { 0,0,-1,-1,-1,0,1,1,1 };
int dc[9] = { 0,-1,-1,0,1,1,1,0,-1 };

void init() {
	for (int i = 0; i < 51; i++) {
		memset(visited[i], false, sizeof(51));
		memset(map[i], 0, sizeof(51));
	}

	movement.clear();
	cloud.clear();
}

void input() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	//freopen("input.txt", "r", stdin);

	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> map[i][j];
		}
	}

	for (int i = 0; i < M; i++) {
		int d, s;
		cin >> d >> s;
		movement.push_back({ d,s });
	}
}

bool inRange(int r, int c) {
	return r >= 1 && r <= N && c >= 1 && c <= N;
}

void print() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cout << map[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}

void solve(int d, int s) {
	vector< pair<int,int> > new_cloud;
	//1,2번
	for (int i = 0; i < cloud.size(); i++) {
		int row = cloud[i].first;
		int col = cloud[i].second;

		int nr = row + dr[d] * (s%N);
		int nc = col + dc[d] * (s%N);
		if (nr < 1) nr = N + nr;
		else if (nr > N) nr = nr - N;

		if (nc < 1) nc = N + nc;
		else if (nc > N) nc = nc - N;

		visited[nr][nc] = true;
		map[nr][nc]++;
		new_cloud.push_back({ nr, nc });
	}
	cloud.clear();

	//4번
	for (int i = 0; i < new_cloud.size(); i++) {
		int row = new_cloud[i].first;
		int col = new_cloud[i].second;

		int cnt = 0; //물이 있는 바구니 수
		for (int k = 2; k <= 8; k += 2) {
			int nr = row + dr[k];
			int nc = col + dc[k];

			if (inRange(nr, nc)) { //경계에 있는 경우
				if (map[nr][nc] > 0) {
					cnt++;
				}
			}
		}
		map[row][col] += cnt;
	}
	//3번
	new_cloud.clear();


	//5번
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (!visited[i][j] && map[i][j] >= 2) {
				cloud.push_back({ i,j });
				map[i][j] -= 2;
			}
		}
	}

	//visited 초기화
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			visited[i][j] = false;
		}
	}
}

int main() {

	init();
	input();

	//초기 구름
	cloud.push_back({ N,1 });
	cloud.push_back({ N,2 });
	cloud.push_back({ N - 1,1 });
	cloud.push_back({ N - 1,2 });
	for (int i = 0; i < M; i++) {
		solve(movement[i][0], movement[i][1]);
	}
	int answer = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			answer += map[i][j];
		}
	}
	cout << answer << endl;

	return 0;
}