สมมติว่าเรามีสตริงที่มีเพียง L และ R ซึ่งหมายถึงการหมุนซ้ายและการหมุนขวาตามลำดับ เราต้องหาทิศทางสุดท้ายของเดือย นี่คือทิศทางเหนือ (N) ตะวันออก (E) ใต้ (S) และตะวันตก (W) เรากำลังสมมติว่าเดือยชี้ไปทางทิศเหนือ (N) ในเข็มทิศ
ดังนั้น หากอินพุตเป็นเหมือน "RRLRLLR" เอาต์พุตจะเป็น E เนื่องจากทิศทางเริ่มต้นคือ N, RR จะชี้ไปที่ S จากนั้น LR จะชี้ไปที่ N เดิมอีกครั้ง จากนั้น LL จะชี้ไปที่ตำแหน่งก่อนหน้า N แล้ว R จะชี้ไปที่ E ดังนั้น E จึงเป็นที่สิ้นสุด
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
นับ :=0
-
ทิศทาง :=สตริงว่าง
-
สำหรับการเริ่มต้น i :=0, เมื่อ i − ความยาวของ s, อัปเดต (เพิ่ม i ขึ้น 1), ทำ −
-
ถ้า s[i] เหมือนกับ 'L' แล้ว −
-
(ลดจำนวนลง 1)
-
-
มิฉะนั้น
-
(เพิ่มจำนวนขึ้น 1)
-
-
-
ถ้านับ> 0 แล้ว −
-
หากการนับ mod 4 เหมือนกับ 0 ดังนั้น −
-
ทิศทาง :="N"
-
-
มิฉะนั้นเมื่อการนับ mod 4 เหมือนกับ 1 ดังนั้น −
-
ทิศทาง :="E"
-
-
มิฉะนั้นเมื่อการนับ mod 4 เหมือนกับ 2 ดังนั้น −
-
ทิศทาง :="ส"
-
-
มิฉะนั้นเมื่อการนับ mod 4 เหมือนกับ 3 ดังนั้น −
-
ทิศทาง :="W"
-
-
-
ถ้านับ <0 แล้ว −
-
หากการนับ mod 4 เหมือนกับ 0 ดังนั้น −
-
ทิศทาง :="N"
-
-
มิฉะนั้นเมื่อการนับ mod 4 เหมือนกับ -1 ดังนั้น −
-
ทิศทาง :="W"
-
-
มิฉะนั้นเมื่อการนับ mod 4 เหมือนกับ -2 ดังนั้น −
-
ทิศทาง :="ส"
-
-
ในทางกลับกันเมื่อการนับ mod 4 เหมือนกับ -3 แล้ว −
-
ทิศทาง :="E"
-
-
-
ทิศทางกลับ
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#include<bits/stdc++.h>
using namespace std;
string get_dir(string s) {
int count = 0;
string direction = "";
for (int i = 0; i < s.length(); i++){
if (s[0] == '\n')
return NULL;
if (s[i] == 'L')
count--;
else
count++;
}
if (count > 0){
if (count % 4 == 0)
direction = "N";
else if (count % 4 == 1)
direction = "E";
else if (count % 4 == 2)
direction = "S";
else if (count % 4 == 3)
direction = "W";
}
if (count < 0){
if (count % 4 == 0)
direction = "N";
else if (count % 4 == -1)
direction = "W";
else if (count % 4 == -2)
direction = "S";
else if (count % 4 == -3)
direction = "E";
}
return direction;
}
int main() {
string s = "RRLRLLR";
cout << (get_dir(s));
} อินพุต
"RRLRLLR"
ผลลัพธ์
E
