資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++ 迷宮逃脫可能性
在這個問題中，我們給定一個由 n 個整數構成的迷宮，每個整數表示需要移動的步數，以及用 ‘>’ 和 ‘<’ 表示的方向。我們的任務是判斷從索引 0 位置出發，是否能夠走出迷宮。
讓我們透過一個例子來理解這個問題
輸入 −
3 2 1 1 4 > < > >
輸出 − YES
解釋 − 從起點開始，我們將向前移動 2 個位置，然後向前移動 1 個位置，然後向前移動 4 個位置。這將使我們走出迷宮。
為了解決這個問題，我們將檢查是否能夠走出迷宮。為此，我們需要走到小於 0 或大於 n 的位置。從 0 開始，我們將根據給定的整數位數和符號處理方向，並檢查是否到達終點。
可能出現的另一個情況是無限迴圈，即使用者永遠無法走出迷宮的情況，這種情況發生在我們回到之前訪問過的位置時。因此，為了檢查這種情況，我們將標記所有已訪問的位置。
示例
程式演示了我們解決方案的實現
#include <iostream>
using namespace std;
void isMazeSolvable (int a[], int n, string s){
int mark[n] = {0};
int start = 0;
int possible = 1;
while (start >= 0 && start < n){
if (s == "<"){
if (mark[start] == 0){
mark[start] = 1;
start -= a[start];
} else {
possible = 0;
break;
}
} else {
if (mark[start] == 0){
mark[start] = 1;
start += a[start];
} else {
possible = 0;
break;
}
}
}
if (possible == 0)
cout << "It stays inside the maze forever";
else
cout << "It will come out of the maze";
}
int main (){
int n = 3;
string s = ">><";
int a[] = { 1, 2, 4 };
isMazeSolvable (a, n, s);
}輸出
It will come out of the maze
更新於: 2020年4月17日
220 次瀏覽
廣告