質問する

ロボット掃除機がある場合は、清掃領域の個数を計算するプログラムを作成してください.
ロボット掃除機があるところはNです×Mサイズの長方形として表示できます.
1×1サイズの正方形の格子に分けます.
各格子は壁またはスペースです.
掃除機は向きがあり、この方向は東、西、南、北の一つです.
地図の各セルは(r,c)で表すことができる.
rは北から来た格の個数、cは西から来た格の個数である.

(0,0)  (0,1)
(1,0)  ...

ロボット掃除機の動作原理は以下の通りです.

現在位置をクリアします.

現在位置で、現在の方向を基準にして、左側から隣接するセルを順にナビゲートします.
A.左の方向に掃除していないところがあれば、
その方向に回転して、1番から1段進みます.
B.左側に清掃スペースがなければ、
その方向に回転して2番に戻ります.
C.4方向の清掃や壁の場合、
眺める方向を保ち、1段後退して2番に戻ります.
D.4つの方向がすでに掃除されているか壁で、後ろの方向が壁で、バックできない場合
運転を止める.

ロボット掃除機は掃除した部屋を掃除しなくなり、壁を通ることができません.

入力

第1行は、縦方向サイズNおよび横方向サイズMを与える.(3 ≤ N, M ≤ 50)
2行目は、ロボット掃除機が位置するセルの座標(r,c)と向きdを示す.
dが0の場合、北へ.
1なら東へ、
2なら南を選び、
3なら西を見ることです.
3行目からN行目では,場所の状態は北から南へ順に,各行は西から東へ順次であった.スペースは0、壁は1です.
地図の最初の行、最後の行、最初の列、最後の列のすべてのセルは壁です.
ロボット掃除機のある部屋の状態はいつも空いています.

に答える

📍 に答える

プログラム動作方式:歩ける場所まで歩いて、バックを止められて、バックして終わります
➡️ DFS

現在位置でDFSを使用して清掃を行い、渋滞するとバックし、バックする場所が壁であれば

を終了する.

DFSは帰航路を介して

を実現する.

ロボット掃除機の情報:座標(r,c)、向き(d)

方向の場合は常にdx,dy宣言(direction of x,y)

// map 구상에 따라서
// 북, 동, 남, 서
int dx[4] = { -1, 0, 1, 0 }
int dy[4] = { 0, 1, 0, -1 }

-DFSを使用してクリーンアップする場合は、常に4方向左にドラッグします.
-dir=0:上、1:あ、2:あ、3:左

for (int i=0; i<4; i++)
	int next_dir = (dir + 3 - i) % 4;

📍 コード#コード#

#include <iostream>
using namespace std;

#define MAX 50
int N, M;
int visited_count;
int map[MAX][MAX]; // 지도
int visited[MAX][MAX] = {
    0,
}; // 청소기 경로,  방문했으면 1

// 북, 동, 남, 서
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
int r, c, d;

void Input()
{
    cin >> N >> M;
    cin >> r >> c >> d;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> map[i][j];
        }
    }

    visited[r][c] = 1;
    visited_count++;
}

void dfs()
{
    // 네 방향 청소, 계속 왼쪽으로 회전
    for (int i = 0; i < 4; i++)
    {
        int next_d = (d + 3 - i) % 4; // next direction (왼쪽)
        int next_r = r + dx[next_d];
        int next_c = c + dy[next_d];

        // B. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
        if (next_r < 0 || next_r >= N || next_c < 0 || next_c >= M || map[next_r][next_c] == 1)
        {
            continue;
        }

        // A. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
        if (map[next_r][next_c] == 0 && visited[next_r][next_c] == 0)
        {
            visited[next_r][next_c] = 1;
            r = next_r;
            c = next_c;
            d = next_d;
            visited_count++;
            dfs();
        }
    }

    int back_idx = d > 1 ? d - 2 : d + 2;
    int back_r = r + dx[back_idx];
    int back_c = c + dy[back_idx];
    // C. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는,
    if (back_r >= 0 && back_r <= N || back_c >= 0 || back_c <= M)
    {
        // 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
        if (map[back_r][back_c] == 0)
        {
            r = back_r;
            c = back_c;
            dfs();
        }
        // D. 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.
        else
        {
            cout << visited_count << endl;
            exit(0);
        }
    }
}

int main()
{
    Input();
    dfs();

    return 0;
}