[白俊14503]ロボット掃除機


質問ビュー:機械掃除機
難易度:金貨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";
    }