e585 - 12797 - Letters
題目描述
題目要求計算從一個 N x N 的公園左上角到右下角的最短一致路徑長度。公園的每個格子包含一個字母，可以是前 10 個大寫字母或前 10 個小寫字母。一致路徑的定義是，一旦選擇了大寫字母，後續只能走大寫字母；一旦選擇了小寫字母，後續只能走小寫字母。如果不存在一致路徑，則輸出 -1。
解題思路
本題採用深度優先搜尋 (DFS) 搭配廣度優先搜尋 (BFS) 的方式來解決。首先，使用 DFS 窮舉所有可能的字母選擇（大寫或小寫），對於每種選擇，使用 BFS 尋找從起點到終點的最短路徑。DFS 的作用是確定路徑的一致性，即所有字母都是大寫或小寫。BFS 的作用是尋找在一致性約束下，最短的路徑長度。如果 BFS 找到路徑，則更新最短路徑長度。如果 DFS 窮舉所有可能的選擇後，仍然沒有找到路徑，則輸出 -1。
複雜度分析
- 時間複雜度: O(2^10 * N^2 * N^2)。其中 2^10 是 DFS 窮舉所有字母大小寫組合的數量，N^2 是公園的大小，N^2 是 BFS 的最壞情況複雜度。
- 空間複雜度: O(N^2)。主要由 BFS 的隊列和
has陣列佔用。
程式碼
#include <bits/stdc++.h>
using namespace std;
int n,w[4][2]={{0,1},{0,-1},{1,0},{-1,0}},ans;
bool cu[20],has[105][105];
char a[105][105];
void bfs(){
int ct=0,cnt=1;
queue <pair <int,int>> q; // used x y
memset(has,0,sizeof(has));
if(cu[a[0][0]]==0)return;
q.push({0,0});
while(!has[n-1][n-1]&&!q.empty()&&ct<ans){
++ct;
queue <pair <int,int>> nxt;
while(!q.empty()){
pair <int,int> tp = q.front();
int x=tp.first,y=tp.second;
q.pop();
if(has[x][y])continue;
has[x][y]=1;
for(int i=0;i<4;++i){
int xt=x+w[i][0],yt=y+w[i][1];
if(xt>=0&&xt<n&&yt>=0&&yt<n&&cu[a[xt][yt]])
nxt.push({xt,yt});
}
}
q=nxt;
}
if(has[n-1][n-1])ans=ct;
return;
}
void dfs(int it){
if(it==10){
bfs();
return;
}
cu[it]=1;
cu[it+10]=0;
dfs(it+1);
cu[it]=0;
cu[it+10]=1;
dfs(it+1);
}
int main(){
cin.tie(0);cout.tie(0); ios::sync_with_stdio(false);
while(cin >> n){
for(int i=0;i<n;++i)
for(int j=0;j<n;++j){
cin >> a[i][j];
if(a[i][j]>='a')a[i][j]=a[i][j]-'a'+'A'+10;
a[i][j]-='A';
}
if(abs(a[0][0]-a[n-1][n-1])==10){
cout << "-1\n";
continue;
}
ans=10000;
dfs(0);
if(ans==10000){
cout << "-1\n";
}
else{
cout << ans << '\n';
}
}
}