يمثل صفيف M × N المستطيل المتاهة ، و 0 و 1 يمثلان المسارات والعقبات في المتاهة ، على التوالي. صمم برنامجًا للعثور على مسار من مدخل المخرج لأي متاهة إعداد ، أو استخلاص أنه لا يوجد مسار.
(1) إخراج الرسم البياني للمتاهة وفقًا للمصفوفة ثنائية الأبعاد.
(2) استكشاف الاتجاهات الأربعة للمتاهة: اليمين إلى اليمين ، أسفل إلى أسفل ، اليسار إلى اليسار ، وأعلى إلى أعلى ، وإخراج مسار المشي من مدخل المخرج.
مثال:
الزاوية العلوية اليسرى (1 ، 1) هي المدخل ، والركن الأيمن السفلي (8 ، 9) هو المخرج.
يمكنك استخدام طريقة التراجع ، أي بدءًا من المدخل والاستكشاف في اتجاه معين. إذا كان من الممكن القيام به ، فاستمر في المضي قدمًا ؛ خلاف ذلك ، تتراجع على طول المسار الأصلي ، واصل الاستكشاف في اتجاه آخر حتى موضع الخروج ، وإيجاد مسار. إذا تم استكشاف جميع المسارات الممكنة ولم يتم الوصول إلى الخروج ، فإن مجموعة المتاهة لا تحتوي على مسارات.
استيراد java.util.*؛ موضع الفئة {public position () {} الموضع العام (int row ، int col) {this.col = col ؛ this.row = row ؛ } السلسلة العامة toString () {return "(" + row + "،" + col + ")" ؛ } int row ؛ int col ؛} class maze {public maze () {maze = new int [15] [15] ؛ stack = مكدس جديد <potort> () ؛ P = New Boolean [15] [15] ؛ } /** Constructing Maze* / public void init () {scanner scanner = new Scanner (system.in) ؛ System.out.println ("الرجاء إدخال عدد صفوف المتاهة") ؛ ROW = SCANNER.NEXTINT () ؛ System.out.println ("الرجاء إدخال عدد أعمدة المتاهة") ؛ col = scanner.nextint () ؛ System.out.println ("الرجاء إدخال" ROW + "ROW" + COL + "Column Maze") ؛ int temp = 0 ؛ لـ (int i = 0 ؛ i <row ؛ ++ i) {for (int j = 0 ؛ j <col ؛ ++ j) {temp = scanner.nextint () ؛ متاهة [i] [j] = temp ؛ p [i] [j] = false ؛ }}} /** عد إلى المتاهة لمعرفة ما إذا كان هناك طريقة للخروج* / public void findPath () {// أعط دائرة من الجدران حول منازل المتاهة الأصلية int temp [] = new int [row + 2] [col + 2] ؛ لـ (int i = 0 ؛ i <row +2 ؛ ++ i) {for (int j = 0 ؛ j <col +2 ؛ ++ j) {temp [0] [j] = 1 ؛ درجة الحرارة [الصف + 1] [j] = 1 ؛ temp [i] [0] = temp [i] [col + 1] = 1 ؛ }} // انسخ المتاهة الأصلية في المتاهة الجديدة لـ (int i = 0 ؛ i <row ؛ ++ i) {for (int j = 0 ؛ j <col ؛ ++ j) {temp [i +1] [j +1] = maze [i] [j] ؛ }} // ابدأ الاستعلام في اتجاه عقارب الساعة من الزاوية اليسرى العليا int i = 1 ؛ int j = 1 ؛ p [i] [j] = true ؛ Stack.push (موقف جديد (I ، J)) ؛ بينما (! stack.empty () && (! (i == (row) && (j == col)))))) {if ((temp [i] [j + 1] == 0) && (p [i] [j + 1] == false)) {p [i] [j + 1] = true ؛ stack.push (موضع جديد (i ، j + 1)) ؛ J ++ ؛ } آخر إذا ((temp [i + 1] [j] == 0) && (p [i + 1] [j] == false)) {p [i + 1] [j] = true ؛ Stack.push (موضع جديد (i + 1 ، j)) ؛ i ++ ؛ } آخر إذا ((temp [i] [j - 1] == 0) && (p [i] [j - 1] == false)) {p [i] [j - 1] = true ؛ stack.push (موقف جديد (i ، j - 1)) ؛ ي-؛ } آخر إذا ((temp [i - 1] [j] == 0) && (p [i - 1] [j] == false)) {p [i - 1] [j] = true ؛ Stack.push (موقف جديد (I - 1 ، J)) ؛ أنا--؛ } آخر {stack.pop () ؛ if (stack.empty ()) {break ؛ } i = stack.peek (). row ؛ j = stack.peek (). col ؛ }} stack <port> newPos = new stack <porting> () ؛ if (stack.empty ()) {break ؛ } i = stack.peek (). row ؛ j = stack.peek (). col ؛ }} stack <port> newPos = new stack <porting> () ؛ if (stack.empty ()) {system.out.println ("no path") ؛ } آخر {system.out.println ("هناك مسار") ؛ System.out.println ("المسار كما يلي:") ؛ بينما (! stack.empty ()) {position pos = new position () ؛ pos = stack.pop () ؛ newpos.push (pos) ؛ }} / * * مسار الإخراج الرسومي * * / السلسلة نتيجة [] [] = سلسلة جديدة [صف+1] [COL+1] ؛ لـ (int k = 0 ؛ k <row ؛ ++ k) {for (int t = 0 ؛ t <col ؛ ++ t) {result [k] [t] = (maze [k] [t])+"" ؛ }} بينما (! newPos.Empty ()) {position p1 = newPos.pop () ؛ النتيجة [P1.ROW-1] [P1.COL-1] = "#" ؛ } لـ (int k = 0 ؛ k <row ؛ ++ k) {for (int t = 0 ؛ t <col ؛ ++ t) {system.out.print (resault [k] [t]+"/t") ؛ } system.out.println () ؛ }} int maze [] [] ؛ Private int Row = 9 ؛ Private Int Col = 8 ؛ مكدس <posit> مكدس ؛ Boolean P [] [] = null ؛} class hello {public static void main (string [] args) {maze demo = new maze () ؛ demo.init () ؛ demo.findpath () ؛ }} مثال على الجري:
الرجاء إدخال عدد صفوف المتاهة
3
الرجاء إدخال عدد الأعمدة في المتاهة
3
الرجاء إدخال متاهة من 3 صفوف و 3 أعمدة
0 1 1
0 0 1
1 0 0
المسارات كما يلي:
الرجاء إدخال عدد صفوف المتاهة
9
الرجاء إدخال عدد الأعمدة في المتاهة
8
الرجاء إدخال متاهة من 9 صفوف و 8 أعمدة
0 0 1 0 0 1 0
0 0 1 0 0 1 0
0 0 1 0 1 0 1
0 1 1 1 0 0 1 0
0 0 0 1 0 0 0
0 1 0 0 0 1 0 1
0 1 1 1 1 0 0 1
1 1 0 0 0 1 0 1
1 1 0 0 0 0 0 0
المسارات كما يلي:
ما سبق هو كل محتوى هذه المقالة. آمل أن يكون ذلك مفيدًا لتعلم الجميع وآمل أن يدعم الجميع wulin.com أكثر.