14503 로봇청소기

1. 문제

 

2. 코드

#include <iostream>

using namespace std;
int N, M;
int x, y, d;
//서 남 동 북
// 0: 북 1:동 2:남 3: 서          2번째는 후진했을 때 위치
int dir[4][4][2] = { { {0,-1},{1,0},{0,1},{-1,0} }, //서 남 동 북
				   { {-1,0},{0,-1},{1,0},{0,1} }, //북 서 남 동 
					{ {0,1},{-1,0},{0,-1},{1,0} }, //동 북 서 남
					{ {1,0},{0,1},{-1,0},{0,-1} } }; //남 동 북 서 
int towards[4][4] = {
					{3,2,1,0},
					{0,3,2,1},
					{1,0,3,2},
					{2,1,0,3}};

int map[50][50];
int cnt = 1;

int dfs(int x, int y, int d);

int main() {
	cin >> N >> M;
	cin >> x >> y >> d;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
			if (map[i][j] == 1)
				map[i][j] = -1;
		}
	}

	cout << dfs(x, y, d);
	/*
	cout << endl;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			printf("%4d", map[i][j]);
		}
		printf("\n");
	}
	*/
}

//방향에 따라 탐색 순서를 바꿔야 한다. 
int dfs(int x, int y, int d) {
	//cout << x << " " << y << " " << d << endl;
	map[x][y] = cnt++;
	for (int i = 0; i < 4; i++) {
		int nx = x + dir[d][i][0];
		int ny = y + dir[d][i][1];

		if (map[nx][ny] != 0) {
			//사방이 벽이거나 이미 청소한 곳일때
			if (i == 3) {
				//후진했을 때 벽이면
				if (map[x + dir[d][1][0]][y + dir[d][1][1]] == -1) {
					return cnt-1;
				}
				//방향은 그대로 두고 후진
				cnt--;
				return dfs(x + dir[d][1][0], y + dir[d][1][1], d);
			}
			continue;
		}
		return dfs(nx, ny, towards[d][i]);
	}
}