백준 8972번 미친 아두이노 C++

출처 : https://www.acmicpc.net/problem/8972

 

1. 내 아두이노를 방향에 맞게 이동시킨다. 이때, 이동한 곳에 미친 아두이노가 있으면 종료한다.

2. 미친 아두이노를 내 아두이노의 거리가 가장 짧게 되는 지점으로 이동시킨다.

3. 모든 미친 아두이노를 이동시킨 뒤 한 공간에 두 개 이상의 미친 아두이노가 있으면 그 공간에 있는 모든 아두이노를 없앤다.

4. 미친 아두이노가 내 아두이노와 만났다면 종료한다.

#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 <unordered_map>
#include <unordered_set>

using namespace std;
using ll = long long;

int r, c;
string moveStr;

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

void PrintBoard(const vector<vector<char>>& board) {
	for (auto a : board) {
		for (auto b : a) {
			cout << b;
		}
		cout << "\n";
	}
	cout << "\n";
}

bool MoveMyArd(pair<int, int>& myArd, vector<vector<char>>& board, int dir) {
	int nextRow = myArd.first + dRow[dir];
	int nextCol = myArd.second + dCol[dir];
	if (board[nextRow][nextCol] == 'R') return false;
	board[myArd.first][myArd.second] = '.';
	myArd.first = nextRow;
	myArd.second = nextCol;
	board[myArd.first][myArd.second] = 'I';
	return true;
}

int GetMinDistDir(const pair<int, int>& target, int row, int col) {
	int minDist = 10000;
	int ret = -1;
	for (int i = 0; i < 9; i++) {
		int nextRow = row + dRow[i];
		int nextCol = col + dCol[i];
		if (nextRow < 0 || nextRow >= r) continue;
		if (nextCol < 0 || nextCol >= c) continue;
		int dist = abs(target.first - nextRow) + abs(target.second - nextCol);
		if (dist < minDist) {
			minDist = dist;
			ret = i;
		}
	}
	return ret;
}

bool MoveCrazyArd(const pair<int, int>& myArd, vector<vector<char>>& board, 
	vector<pair<int, int>>& crazy_Ards) {

	vector<vector<int>> crazy_Ards_Cnt(r, vector<int>(c, 0));
	for (int i = 0; i < crazy_Ards.size(); i++) {		
		int dir = GetMinDistDir(myArd, crazy_Ards[i].first, crazy_Ards[i].second);
		int nextRow = crazy_Ards[i].first + dRow[dir];
		int nextCol = crazy_Ards[i].second + dCol[dir];
		if (board[nextRow][nextCol] == 'I') return false;
		board[crazy_Ards[i].first][crazy_Ards[i].second] = '.';
		crazy_Ards[i].first = nextRow;
		crazy_Ards[i].second = nextCol;
		crazy_Ards_Cnt[crazy_Ards[i].first][crazy_Ards[i].second]++;
	}
	for (auto it = crazy_Ards.begin(); it != crazy_Ards.end();) {
		int row = it->first;
		int col = it->second;
		if (crazy_Ards_Cnt[row][col] > 1) {
			it = crazy_Ards.erase(it);
			continue;
		}
		board[row][col] = 'R';
		++it;
	}

	return true;
}

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

	cin >> r >> c;
	pair<int, int> myArd;
	vector<vector<char>> board(r, vector<char>(c));
	vector<pair<int, int>> crazy_Ards;
	vector<int> moveVec;

	for (int i = 0; i < r; i++) {
		string str;
		cin >> str;
		for (int j = 0; j < c; j++) {
			board[i][j] = str[j];
			if (str[j] == 'I') myArd = { i,j };
			if (str[j] == 'R') crazy_Ards.push_back({ i,j });
		}
	}
	cin >> moveStr;
	for (int i = 0; i < moveStr.length(); i++) {
		int dir = moveStr[i] - '0' - 1;
		moveVec.push_back(dir);
	}
	int cnt = 0;
	for (int i = 0; i < moveVec.size(); i++) {
		cnt++;
		if (!MoveMyArd(myArd, board, moveVec[i])) break;
		if (!MoveCrazyArd(myArd, board, crazy_Ards)) break;
	}

	if (cnt < moveVec.size()) {
		cout << "kraj" << " " << cnt;
	}
	else PrintBoard(board);
};