Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|
Бодолт илгээх Бүх бодолтууд Шилдэг бодолтууд PDF Жагсаалт руу буцах

RGB7794 - Улаан бэрсний хамгийн богино нүүдэл

Ердийн шатарт хар цагаан 2 өнгийн дүрс байдаг бол бидний хувилбарт онцгой нүүдэлтэй өөр өнгийн дүрс бий.

Энэ хувилбарын хүчтэй бодуудын нэг нь улаан бэрс.

Үлаан бэрс тухайн нүднээс доорх зурагт үзүүлсэн 6 нүд рүү нүүх боломжтой.

( зүүн дээд, баруун дээд, баруун, баруун доод, зүүн доод, зүүн).

image

Хөлөг nxn хэмжээтэй.

Хөлгийн нүдийг (I,j) кординат дээр байрлана i – мөрийн дугаар, j – баганын дугаар. 0-с эхлэж дугаарлагдана.

Иймээс зүүн дээд булан (0,0), баруун доод булан (n-1, n-1) кординаттай байна.

Функцын тайлбар

Доор өгөгдсөн хэсэгт printShortestPath функцыг гүйцээж бичнэ үү.

Функцын оролт нь хөлгийн хэмжээ n, болон эхлэл болон төгсгөлийн нүдний кординат байна.

(istart, jstart) (iend, jend). Функц утга буцаахгүй.

Улаан бэрсний эхлэлийн координат болон төгсгөлийн кординат өгөгдөхөд эхэлэлээс төгсгөл хүрэхэд хамгийн бага

алхамын тоог хэвлэнэ үү. Дараа нь хамгийн цөөн нүүдлээр очих нүүдлүүдийг  хэвлэнэ үү.

Хэрвээ төгсгөлийн нүдэнд очих боломжгүй бол “Impossible” гэж хэвлэнэ.

Нэмэлт

Хамгийн богино нүүдэл хэд хэдэн хувилбартай байж болох бөгөөд улаан бэрс нүүдэл сонгохдоо дараахи эрэмбээр сонгодог.

UL, UR, R, LR, LL, L.

Өөрөөр хэлбэл хэд хэдэн боломжит шийдэл байвал салаа замаас нэгийг нь сонгохдоо дээрхи дарааллаар сонгоно.

Жишээ 2-оос энэ дүрмийг харж болно.

Хязгаарлалт

  • 5 <= n <= 200
  • 0<= istart, jstart, iend, jend<n
  • Эхлэл төгсгөлийн нүд давхцахгүй.

Гаралтын формат

Хэрвээ төгсгөлийн нүдэнд очих боломжтой бол 2 мөрөнд хариуг хэвлэнэ.

Эхний нүдэнд хамгийн цөөн нүүдлийн тоог илэрхийлэх тоо байна.

2 дахь мөрөнд нүүдлийн алхамуудыг илэрхийлэх нүүдлийн үсгүүд байна.

Жишээ

Оролт 0

7

6 6 0 1

Гаралт 0

4

UL UL UL L

Тайлбар 0

image

Оролт 1

6
5 1 0 5

Гаралт 1

Impossible

Тайлбар 1

image

Оролт 2

 7

0 3 4 3

Гаралт 2

2

LR LL

Тайлбар 2

image


Орчуулсан : Б.Даваабаяр АНУ

Submit solution!
Нэмсэн:Bataa
Огноо:2020-04-13
Хугацааны хязгаарлалт:1s
Эх кодын хэмжээний хязгаарлалт:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Програмчлалын хэлүүд:ADA95 ASM32 ASM64 BASH BF C NCSHARP CSHARP C++ 4.3.2 CPP C99 CLPS LISP sbcl LISP clisp D ERL FORTRAN HASK ICON ICK JAVA JS-RHINO JULIA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON PYPY3 PYTHON3 RUBY SCALA SCM guile ST TCL WHITESPACE
Эх сурвалж:https://www.hackerrank.com/challenges/red-knights-shortest-path/problem
hide comments
2023-03-26 17:55:40
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int n;
int rowStart, colStart;
int rowEnd, colEnd;

void printBoard(vector<vector<bool>> &);
int main() {
cin >> n;
cin >> rowStart >> colStart >> rowEnd >> colEnd;

vector<vector<bool>> board(n);
for (int i = 0; i < n; i++) {
board[i] = vector<bool>(n, false);
}
board[rowStart][colStart] = true;

/*Exception checking*/
if(abs(rowEnd - rowStart) % 2 != 0 ) {
cout << "Impossible";
return 0;
}
else {
int rowMovement = abs(rowEnd - rowStart) / 2;
if(rowMovement % 2 == 0) {
if(abs(colEnd - colStart) % 2 != 0) {
cout << "Impossible";
return 0;
}
}
if(rowMovement % 2 == 1) {
if(abs(colEnd - colStart) % 2 == 0) {
cout << "Impossible";
return 0;
}
}
}
/*-------------------------------------------------------------*/

vector<string> path;

int movement = 0;
while(rowStart != rowEnd || colStart != colEnd) {
while((rowEnd - rowStart) < 0 && (colEnd - colStart) <= 0 && (rowStart - 2) >= 0 && (colStart - 1) >= 0) {
rowStart -= 2;
colStart -= 1;
board[rowStart][colStart] = true;
movement++;
path.push_back("UL ");
}
while((rowEnd - rowStart) < 0 && (colEnd - colStart) >= 0 && (rowStart - 2) >= 0 && (colStart + 1) < n) {
rowStart -= 2;
colStart += 1;
board[rowStart][colStart] = true;
movement++;
path.push_back("UR ");
}
if((colEnd - colStart) > 0) {
int rowMovement = (rowEnd - rowStart) / 2;
while((rowEnd - rowStart) == 0 && (colEnd - colStart) > 0 && (colStart + 2) < n) {
colStart += 2;
board[rowStart][colStart] = true;
movement++;
path.push_back("R ");
}
while(((colEnd - rowMovement * 1) - colStart) > 0 && (colStart + 2) < n) {
colStart += 2;
board[rowStart][colStart] = true;
movement++;
path.push_back("R ");
}

}
while((rowEnd - rowStart) > 0 && (colEnd - colStart) >= 0 && (rowStart + 2) < n && (colStart + 1) < n) {
rowStart += 2;
colStart += 1;
board[rowStart][colStart] = true;
movement++;
path.push_back("LR ");
}
while((rowEnd - rowStart) > 0 && (colEnd - colStart) <= 0 && (rowStart + 2) < n && (colStart - 1) >= 0) {
rowStart += 2;
colStart -= 1;
board[rowStart][colStart] = true;
movement++;
path.push_back("LL ");
}
while((rowEnd - rowStart) == 0 && (colEnd - colStart) < 0 && (colStart - 2) >= 0) {
colStart -= 2;
board[rowStart][colStart] = true;
movement++;
path.push_back("L ");
}
}

cout << movement << endl;
for(auto str : path) {
cout << str;
}
}

void printBoard(vector<vector<bool>> &board) {
cout << endl;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << board[i][j] << " ";
}
cout << endl;
}
}

Source code by JacKeR*
try printBoard() for speculation
2022-04-22 06:42:12
zarna 88273717 zalgaad hohood awarai
2022-03-24 03:49:57
21tei huurhun anai bn, duudlagaar ochino 86376834
2020-11-24 07:46:05
90150454ruu zalgaarai
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.