백준 14503 : 로봇 청소기 (Gold 5)

문제

---

백준 14503 : 로봇 청소기 (Gold 5)

문제 해석

---

시뮬레이션 문제.

 

문제에서 말하는 그대로 구현하면 됩니다.

 

그러나 문제 설명에서 후진하는 시점이 조금 애매한데

두 번째 예제처럼 출력이 나오려면 네 방향 모두 청소할 수 없음을 알아챈 순간 왼쪽으로 회전하지 않고 후진해야 합니다. 

 

통찰

---

구현 문제이기 때문에 통찰이 필요없습니다.

 

시간 복잡도

---

4 * n * m = 4 * 50 * 50 = 10000 < 20억 (2초)

n * m 만큼의 칸에서 4방향 모두 탐색

풀이

---

/**
 * @template file author kadrick (kbk2581553@gmail.com)
 *
 * author:amkorousagi (hasmi5452@gmail.com)
 */
#include <bits/stdc++.h>
using namespace std;
#define fastio                                                                 \
  ios::sync_with_stdio(false);                                                 \
  cin.tie(0);
#define endl '\n'

vector<vector<int>> mmap;
int n, m, r, c, d;
int cnt;



void clean(int cr, int cc, int cd, int ro) {
	//cout << cr << " " << cc <<" "<< cd<<" "<<ro << endl;
	if (mmap[cr][cc] == 0) {
		cnt++;
		mmap[cr][cc] = 2;
	}	

	int nr, nc, nd;

	if (ro == 4) {
		nd = (cd) % 4;
		if (nd == 0) {
			nr = cr+1;
			nc = cc;
		}else if (nd == 1) {
			nr = cr;
			nc = cc-1;
		}
		else if (nd == 2) {
			nr = cr-1;
			nc = cc;
		}
		else if (nd == 3) {
			nr = cr;
			nc = cc+1;
		}
		nd = (cd + 2) % 4;

		if (mmap[nr][nc] == 1) {
			return;
		}
		else {
			clean(nr, nc, cd, 0);
		}
		return;
	}

	if (cd == 0) {
		nr = cr;
		nc = cc-1;
		nd = 3;
		if (mmap[nr][nc] == 0) {
			clean(nr, nc, nd, 0);
		}
		else {
			clean(cr, cc, nd, ro + 1);
		}
	}else if (cd == 1) {
		nr = cr - 1;
		nc = cc;
		nd = 0;
		if (mmap[nr][nc] == 0) {
			clean(nr, nc, nd, 0);
		}
		else {
			clean(cr, cc, nd, ro + 1);
		}
	}
	else if (cd == 2) {
		nr = cr;
		nc = cc + 1;
		nd = 1;
		if (mmap[nr][nc] == 0) {
			clean(nr, nc, nd, 0);
		}
		else {
			clean(cr, cc, nd, ro + 1);
		}
	}
	else if (cd == 3) {
		nr = cr + 1;
		nc = cc;
		nd = 2;
		if (mmap[nr][nc] == 0) {
			clean(nr, nc, nd, 0);
		}
		else {
			clean(cr, cc, nd, ro + 1);
		}
	}
}

int main(void) {
	fastio;
	
	cin >> n >> m;
	cin >> r >> c >> d;

	mmap.assign(n, vector<int>(m));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> mmap[i][j];
		}
	}
	clean(r, c, d, 0);

	cout << cnt;
	return 0;
}