a280 - 小朋友上樓梯
題目描述
題目描述一個圖，其中節點代表樓梯的階數，邊代表傳送管道。目標是判斷從 0 階樓梯是否能到達 n 階樓梯。
解題思路
這題可以使用深度優先搜尋 (DFS) 來解決。我們可以將樓梯的階數視為圖的節點，傳送管道視為圖的邊。從 0 階樓梯開始進行 DFS，如果能到達 n 階樓梯，則輸出 "Ok!"，否則輸出 "Impossib1e!"。為了避免無限迴圈，在 DFS 過程中，我們需要將已經訪問過的節點標記為已訪問，防止重複訪問。程式碼中，a[no][i] = 0 的作用就是標記從 no 到 i 的邊已經走過，避免重複走訪。
複雜度分析
- 時間複雜度: O(V + E)，其中 V 是樓梯階數的數量 (最多 101)，E 是傳送管道的數量 (最多 10000)。在最壞情況下，DFS 需要遍歷所有節點和邊。
- 空間複雜度: O(V)，主要來自於遞迴呼叫堆疊的空間，以及
a陣列的空間。
程式碼
#include <iostream>
using namespace std;
bool a[101][101],ans=0;
inline void dfs(int no,int g){
if(ans)return;
if(no==g)ans=1;
for(int i=0;i<101;++i){
if(!ans&&a[no][i]){
a[no][i]=0;
dfs(i,g);
}
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int n,k,x,y;
while(cin >> n >> k){
for(int i=0;i<101;++i)
for(int j=0;j<101;++j)
a[i][j]=0;
while(k--){
cin >> x >> y;
a[x][y]=1;
}
ans=0;
dfs(0,n);
if(ans)
cout << "Ok!\n";
else
cout << "Impossib1e!\n";
}
}