質問ビュー:機械掃除機
難易度:金貨5
アルゴリズム分類:実装、シミュレーション

に答える

📌 問題では、与えられた動作条件に従って順次動作し、flagを使用して4つの方向を参照するかどうかを決定する.

へんすう

方向:위、오른쪽、아래、왼쪽、およびdyの順序で定義され、インデックスが減少するにつれて現在の方向から左に回転するようにする.

ロボット掃除機:現在位置dx、_y、現在方向_xを有する.

const int MAX = 50;
int map[MAX][MAX];

// U R D L
const int dy[4] = {-1,0,1,0};
const int dx[4] = {0,1,0,-1};

int N, M;
int nAnswer;

class RobotCleaner
{
public:
	int _y, _x;
	int _dir;

	RobotCleaner()
		: _y(0), _x(0), _dir(0)
	{}
};
RobotCleaner robotCleaner;

シミュレーション

スペースは0、壁は1、掃除が終わったところは2です.

操作を停止する条件を満たすまで無限ループを支援します.

_dirに従って現在の位置をクリアします.掃除した部屋の数を数える조건 1.

void Solve()
{
	// 0: Empty
	// 1: Wall
	// 2: Cleaned
	
	while (true) {
		int cy = robotCleaner._y;
		int cx = robotCleaner._x;

		// Step 1. Clean Current Location
		if (map[cy][cx] == 0) {
			map[cy][cx] = 2;
			nAnswer++;
		}

		/* ... */
}

nAnswerに従い、左に曲がって左側にクリーンアップされていない空き領域が表示されるまで、ナビゲーションを続けます.

最大4回、その場で1回転し、조건 2 flagを使用してナビゲーションが成功したかどうかを確認します.

void Solve()
{
	// 0: Empty
	// 1: Wall
	// 2: Cleaned
	
	while (true) {
		/* ... */
        
		// Step 2. Turn Left
		bool bCleaned = false;
        // 최대 4방향 탐색
		for (int nCnt = 0; nCnt < 4; nCnt++) {
			int curDir = robotCleaner._dir;
			int nextDir = ((--curDir) + 4) % 4;

			int ny = cy + dy[nextDir];
			int nx = cx + dx[nextDir];
			
			if (map[ny][nx] == 0) {
            	// 탐색 성공 시 이동 후 루프 탈출
				robotCleaner._dir = nextDir;
				robotCleaner._y = ny;
				robotCleaner._x = nx;
				bCleaned = true;
				break;
			}
			else if (map[ny][nx] == 1 || map[ny][nx]==2) {
				robotCleaner._dir = nextDir;
				continue;
			}
		}

		/* ... */
}

のナビゲーションに失敗した場合は、バックし、後ろが壁の場合は、これまでクリアしたセル数を停止して印刷します.

void Solve()
{
	// 0: Empty
	// 1: Wall
	// 2: Cleaned
	
	while (true) {
		/* ... */

		// After Search 4 directions
        // 탐색에 실패
		if (!bCleaned) {
			// Go back
			int ny = robotCleaner._y - dy[robotCleaner._dir];
			int nx = robotCleaner._x - dx[robotCleaner._dir];
			
            // 뒤가 벽이라면 멈추고
			if (map[ny][nx] == 1)
				break;
			// 아니면 후진합니다.
			else {
				robotCleaner._y = ny;
				robotCleaner._x = nx;
				continue;
			}
		}
	}
	
    // 청소기가 멈춘 경우 답을 출력합니다.
	std::cout << nAnswer << "\n";
}

Source Code

#include <iostream>

const int MAX = 50;
int map[MAX][MAX];

// U R D L
const int dy[4] = {-1,0,1,0};
const int dx[4] = {0,1,0,-1};

int N, M;
int nAnswer;

class RobotCleaner
{
public:
	int _y, _x;
	int _dir;

	RobotCleaner()
		: _y(0), _x(0), _dir(0)
	{}
};
RobotCleaner robotCleaner;

void Solve();

int main()
{
	// IO Setting
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	// INPUT
	std::cin >> N >> M;
	std::cin >> robotCleaner._y >> robotCleaner._x >> robotCleaner._dir;
	
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			std::cin >> map[y][x];
		}
	}

	Solve();

	return 0;
}

void Solve()
{
	// 0: Empty
	// 1: Wall
	// 2: Cleaned
	
	while (true) {
		int cy = robotCleaner._y;
		int cx = robotCleaner._x;

		// Step 1. Clean Current Location
		if (map[cy][cx] == 0) {
			map[cy][cx] = 2;
			nAnswer++;
		}

		// Step 2. Turn Left
		bool bCleaned = false;
		// 최대 4방향 탐색
		for (int nCnt = 0; nCnt < 4; nCnt++) {
			int curDir = robotCleaner._dir;
			int nextDir = ((--curDir) + 4) % 4;

			int ny = cy + dy[nextDir];
			int nx = cx + dx[nextDir];
			
			if (map[ny][nx] == 0) {
				// 탐색 성공 시 이동 후 루프 탈출
				robotCleaner._dir = nextDir;
				robotCleaner._y = ny;
				robotCleaner._x = nx;
				bCleaned = true;
				break;
			}
			else if (map[ny][nx] == 1 || map[ny][nx]==2) {
				robotCleaner._dir = nextDir;
				continue;
			}
		}

		// After Search 4 directions
		// 탐색에 실패
		if (!bCleaned) {
			// Go back
			int ny = robotCleaner._y - dy[robotCleaner._dir];
			int nx = robotCleaner._x - dx[robotCleaner._dir];

			// 뒤가 벽이라면 멈추고
			if (map[ny][nx] == 1)
				break;
			// 아니면 후진합니다.
			else {
				robotCleaner._y = ny;
				robotCleaner._x = nx;
				continue;
			}
		}
	}

	// 청소기가 멈춘 경우 답을 출력합니다.
	std::cout << nAnswer << "\n";
}