ค้นหาเส้นทางจากเซลล์มุมไปยังเซลล์กลางในเขาวงกตใน C++

สมมติว่าเรามีเขาวงกตสี่เหลี่ยมที่เต็มไปด้วยตัวเลข เราต้องหาเส้นทางทั้งหมดจากเซลล์มุมไปยังเซลล์ตรงกลาง ในที่นี้ เราจะดำเนินการ n ขั้นตอนจากเซลล์ใน 4 ทิศทาง ขึ้น ลง ขวา และซ้าย โดยที่ n คือค่าของเซลล์ ดังนั้น เราสามารถย้ายไปยังเซลล์ [i+n,j] ถึง [i-n, j], [i, j+n] และ [i, j-n] จากเซลล์ [i,j] โดยที่ n คือค่าของเซลล์ [ ผม เจ].

ดังนั้นหากอินพุตเป็นแบบ

แล้วผลลัพธ์ที่ได้จะเป็น

• (0, 0)→(0, 3)→(0, 7)→(6, 7)→(6, 3)→(3, 3)→(3, 4)→(5, 4)→(5 , 2)→(1, 2)→(1, 7)→(7, 7)→(7, 1)→(2, 1)→(5, 1)→(0, 1)→(4, 1 )→(4, 4)→กลาง

• (0, 0)→(0, 3)→(0, 7)→(6, 7)→(6, 3)→(3, 3)→(3, 4)→(5, 4)→(5 , 2)→(1, 2)→(1, 7)→(7, 7)→(7, 1)→(2, 1)→(2, 4)→(4, 4→กลาง

• (0, 0)→(0, 3)→(0, 7)→(0, 1)→(4, 1)→(7, 1)→(2, 1)→(2, 4)→(4 , 4)→กลาง

• (0, 0)→(0, 3)→(0, 7)→(0, 1)→(4, 1)→(4, 4)→กลาง

• (8, 8)→(7, 8)→(4, 8)→(4, 4)→MIDDLE

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ไม่มี :=9

• กำหนดฟังก์ชัน is_ok() ซึ่งจะรับหนึ่งชุดของคู่ที่เรียกว่า visit, หนึ่งคู่ pt,

• คืนค่า จริง เมื่อองค์ประกอบที่หนึ่งและที่สองของ pt ในช่วง 0 ถึง N และ pt ไม่ได้อยู่ในการเยี่ยมชม

• กำหนดอาร์เรย์ dir_row :={ - 1, 1, 0, 0}

• กำหนดอาร์เรย์ dir_col :={ 0, 0, - 1, 1}

• กำหนดแถวอาร์เรย์ :={ 0, 0, N - 1, N - 1}

• กำหนดอาร์เรย์ col :={ 0, N - 1, 0, N - 1}

• กำหนดฟังก์ชัน Solve() นี้จะใช้เขาวงกต เส้นทาง หนึ่งคู่ที่เยี่ยมชม หนึ่งคู่ curr

• ถ้าอันที่หนึ่งและที่สองของเคอร์เนลเท่ากับ N / 2 แล้ว −

  • แสดงเส้นทาง

  • กลับ

• สำหรับการเริ่มต้น i :=0 เมื่อ i <4 อัปเดต (เพิ่ม i ขึ้น 1) ให้ทำ -

  • n :=เขาวงกต[curr.first, curr.second]

  • x :=curr.first + dir_row[i] * n

  • y :=curr.second + dir_col[i] * n

  • n :=คู่ที่ใช้ x, y

  • ถ้า is_ok(เข้าชม ถัดไป) แล้ว −

    • แทรกต่อไปในการเยี่ยมชม

    • แทรกต่อไปที่ส่วนท้ายของเส้นทาง

    • แก้ (เขาวงกต, เส้นทาง, เยี่ยมชม, ถัดไป)

    • ลบองค์ประกอบสุดท้ายออกจากเส้นทาง

    • ลบถัดไปจากการเยี่ยมชม

• จากวิธีหลัก ให้ทำดังนี้ −

• กำหนดคู่หนึ่งชุดที่เรียกว่าเยี่ยมชมแล้ว

• สำหรับการเริ่มต้น i :=0 เมื่อ i <4 อัปเดต (เพิ่ม i ขึ้น 1) ให้ทำ -

  • x :=แถว[i]

  • y :=col[i]

  • pt :=สร้างคู่โดยใช้ (x, y)

  • แทรก pt เข้าเยี่ยมชม

  • แทรก pt ที่ส่วนท้ายของเส้นทาง

  • แก้ (เขาวงกต, เส้นทาง, เยี่ยมชม, pt)

  • ลบองค์ประกอบสุดท้ายออกจากเส้นทาง

  • ลบ pt จากการเยี่ยมชม

ตัวอย่าง (C++)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include using เนมสเปซ std;#define N 9bool is_ok(set> visit, pair pt) { return (pt.first>=0 ) &&(pt.first =0) &&(pt.second > เส้นทาง) { for (auto it =path.begin(); it !=path.end(); it++) cout <<"(" <first <<", " <วินาที <<")->"; cout <<"MIDDLE" <> &path, set> &visited, pair &curr) { if (curr.first ==N / 2 &&curr.second ==N / 2) { display_path ( เส้นทาง); กลับ; } สำหรับ (int i =0; i <4; ++i) { int n =maze[curr.first][curr.second]; int x =curr.first + dir_row[i]*n; int y =curr.วินาที + dir_col[i]*n; คู่ ถัดไป =make_pair(x, y); if (is_ok (เยี่ยมชม, ถัดไป)) { visit.insert (ถัดไป); path.push_back(ถัดไป); แก้(เขาวงกต, เส้นทาง, เยี่ยมชม, ถัดไป); เส้นทาง.pop_back(); visit.erase(ถัดไป); } }} เป็นโมฆะ search_path(int maze[N][N]) { list> path; set> เยี่ยมชม; สำหรับ (int i =0; i <4; ++i) { int x =แถว [i]; int y =col[i]; คู่ pt =make_pair(x, y); visit.insert(pt); เส้นทาง.push_back(จุด); แก้(เขาวงกต, เส้นทาง, เยี่ยมชม, pt); เส้นทาง.pop_back(); visit.erase(จุด); }}int main() { int เขาวงกต[N][N] ={ {3, 4, 4, 4, 7, 3, 4, 6, 3}, {6, 7, 5, 6, 6, 2, 6, 6, 2}, {3, 3, 4, 3, 2, 5, 4, 7, 2}, {6, 5, 5, 1, 2, 3, 6, 5, 6}, {3, 3, 4, 3, 0, 1, 4, 3, 4}, {3, 5, 4, 3, 2, 1, 3, 3, 5}, {3, 5, 4, 3, 2, 6, 4, 4, 3}, {3, 5, 1, 3, 7, 5, 3, 6, 3}, {6, 2, 4, 3, 4, 5, 4, 5, 1} }; search_path(เขาวงกต);}

อินพุต

ผลลัพธ์

(0, 0)->(0, 3)->(0, 7)->(6, 7)->(6, 3)->(3, 3)->(3, 4) ->(5, 4)->(5, 2)->(1, 2)->(1, 7)->(7, 7)->(7, 1)->(2, 1)->(5, 1)->(0, 1)->(4, 1)->(4, 4)->กลาง(0, 0)->(0, 3)->(0, 7)->(6, 7)->(6, 3)->(3, 3)->(3, 4)->(5, 4)->(5, 2)->(1, 2)-> (1, 7)->(7, 7)->(7, 1)->(2, 1)->(2, 4)->(4, 4)->MIDDLE(0, 0)-> (0, 3)->(0, 7)->(0, 1)->(4, 1)->(7, 1)->(2, 1)->(2, 4)->( 4, 4)->MIDDLE(0, 0)->(0, 3)->(0, 7)->(0, 1)->(4, 1)->(4, 4)->MIDDLE (8, 8)->(7, 8)->(4, 8)->(4, 4)->กลาง