AcWing_4318_最短路徑
2022-03-27 02:00 幻霞 閱讀(37) 評論(0) 收藏 舉報鏈接:https://www.acwing.com/problem/content/submission/code_detail/12529624/

這道題目一開始的思路想的太簡單,給出了一個路徑,將這個路徑看做唯一能走的地圖,然后判斷是否有相鄰或者相交,
然而事實上測試樣例中含有像UDR這種東西能夠把標記法直接干碎的數據 (然而事實上是筆者把某一步想的太絕對了)。
因此不能大意,干脆擺爛一下,用默認起點(101,101)讀入路徑后可算出終點(x,y),從終點dfs回起點,更新到達每一個位置的最小長度,然后判斷終點的長度即可。
#include<bits/stdc++.h>
using namespace std;
int m[305][305]= {0};
int ssize;
void dfs(int x,int y,int len) {
static int dx[4]= {-1,1,0,0},dy[4]= {0,0,-1,1};
for(int i=0; i<4; i++) {
int tx=x+dx[i],ty=y+dy[i];
//先計算下一個路徑的值
if(m[tx][ty]==-1) m[tx][ty]=len+1;
}
for(int i=0; i<4; i++) {
int tx=x+dx[i],ty=y+dy[i];
//只有比原來的值小的最優路徑才會去覆蓋
if(m[tx][ty]>=len+1) dfs(tx,ty,len+1);
}
}
int main() {
string s;
cin>>s;
int x=101,y=101;
m[101][101]=-1;
for(int i=0; i<s.size(); i++) {
if(s[i]=='L') x--;
else if(s[i]=='R') x++;
else if(s[i]=='U') y++;
else if(s[i]=='D') y--;
m[x][y]=-1;
}
dfs(x,y,1);
if(m[101][101]<s.size()) cout<<"NO";
else cout<<"YES";
return 0;
}
看到這想到很久以前寫的一些尋路算法,改天研究一下。
浙公網安備 33010602011771號