[白俊14503]ロボット掃除機
29987 ワード
質問ビュー:機械掃除機
難易度:金貨5
アルゴリズム分類:実装、シミュレーション
に答える
方向: ロボット掃除機:現在位置
スペースは0、壁は1、掃除が終わったところは2です.
操作を停止する条件を満たすまで無限ループを支援します.
最大4回、その場で1回転し、
のナビゲーションに失敗した場合は、バックし、後ろが壁の場合は、これまでクリアしたセル数を停止して印刷します. Source Code
難易度:金貨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";
}
Reference
この問題について([白俊14503]ロボット掃除機), 我々は、より多くの情報をここで見つけました
https://velog.io/@ymkwon9413/백준14503-로봇-청소기
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
#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";
}
Reference
この問題について([白俊14503]ロボット掃除機), 我々は、より多くの情報をここで見つけました https://velog.io/@ymkwon9413/백준14503-로봇-청소기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol