i377 - 單字找找看 (Word)
題目描述
題目給定一個由字母組成的矩陣，以及一個目標字串。要求在矩陣中尋找目標字串，字串的字母可以相鄰（上下左右斜角），且每個字母只能使用一次。如果找到字串，則輸出字串起始位置和結束位置的座標。如果找不到，則輸出 "NO"。
解題思路
這題可以使用深度優先搜尋 (DFS) 來解決。首先，遍歷矩陣中的每個格子，如果格子中的字母與目標字串的第一個字母匹配，則從該格子開始進行 DFS 搜尋。在 DFS 搜尋過程中，遞迴地檢查相鄰的格子是否與目標字串的下一個字母匹配。如果找到完整的目標字串，則輸出起始和結束位置的座標。如果遍歷完整個矩陣都找不到目標字串，則輸出 "NO"。
程式碼中 judge 函數實現了 DFS 搜尋。它接收當前位置的座標、搜尋方向和已匹配的字串長度作為參數。如果已匹配的字串長度等於目標字串的長度，則表示找到完整的目標字串，返回 true。如果當前位置超出矩陣範圍或字母不匹配，則返回 false。否則，遞迴地呼叫 judge 函數，檢查相鄰的格子。
複雜度分析
- 時間複雜度: O(n * m * 8^k)，其中 n 和 m 分別是矩陣的行數和列數，k 是目標字串的長度。最壞情況下，需要遍歷矩陣中的每個格子，並從每個格子開始進行 8 個方向的 DFS 搜尋，直到找到目標字串或遍歷完所有可能的路徑。
- 空間複雜度: O(k)，其中 k 是目標字串的長度。空間複雜度主要來自於 DFS 遞迴的堆疊空間，最壞情況下，遞迴深度等於目標字串的長度。
程式碼
#include <iostream>
using namespace std;
int n,m,w[8][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}},ax,ay,tp,dis='a'-'A';
char a[80][80];
string s;
bool judge(int x,int y,int z,int stp){
if(stp==s.size())return 1;
if(x<=0||y<=0||x>n||y>m||a[x][y]!=s[stp])return 0;
return judge(x+w[z][0],y+w[z][1],z,stp+1);
}
int main(){
cin >> n >> m;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j){
cin >> a[i][j];
if(a[i][j]>='A'&&a[i][j]<='Z')
a[i][j]+=dis;
}
cin >> s;
for(int i=0;i<s.size();++i)
if(s[i]>='A'&&s[i]<='Z')
s[i]+=dis;
for(int i=1;i<=n&&!ax;++i)
for(int j=1;j<=m&&!ax;++j)
for(int k=0;k<8&&!ax;++k)
if(judge(i,j,k,0)){
ax=i;
ay=j;
tp=k;
}
if(!ax)
cout << "NO";
else
cout << ax << " " << ay << "\n" << ax+w[tp][0]*(s.size()-1) << " " << ay+w[tp][1]*(s.size()-1);
return 0;
}