k398 - 密室逃脫 (Escape)
題目描述
題目描述一個人在一個 n x m 的地圖上，根據給定的指令字串移動，並標記走過的路徑。指令字串中的每個字元代表一個移動方向，最終輸出地圖，走過的路徑用 '*' 表示，未走過的路徑用 '.' 表示。
解題思路
這題的核心是模擬移動過程。程式首先讀取地圖大小 n 和 m，以及指令字串 s。使用一個二維布林陣列 has[n][m] 記錄每個位置是否被走過。程式根據指令字串中的每個字元，計算下一個位置的座標，如果下一個位置在有效範圍內，則將 has[x][y] 設為 true。最後，遍歷地圖，根據 has[i][j] 的值輸出 '*' 或 '.'。移動方向由 w[i%4][0] 和 w[i%4][1] 定義，分別代表 x 和 y 方向的變化量。
複雜度分析
- 時間複雜度: O(s.size() + n * m)，其中 s.size() 是指令字串的長度，n * m 是地圖的大小。
- 空間複雜度: O(n * m)，主要用於儲存
has陣列。
程式碼
#include <bits/stdc++.h>
using namespace std;
int n,m,x,y,w[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
string s;
bool has[105][105];
int main(){
cin.tie(0); ios::sync_with_stdio(0);
cin >> n >> m >> s;
has[0][0]=1;
for(int i=0;i<s.size();++i){
int ct='0';
while(ct<s[i]){
x+=w[i%4][0];
y+=w[i%4][1];
if(x<0||y<0||x>=n||y>=m){
x-=w[i%4][0];
y-=w[i%4][1];
}
has[x][y]=1;
++ct;
}
}
for(int i=0;i<n;++i){
for(int j=0;j<m;++j){
if(has[i][j]){
cout << "*";
}
else{
cout << ".";
}
}
cout << "\n";
}
}