f418 - Word Search Puzzle
題目描述
題目要求根據給定的字謎大小、起始座標和結束座標，從字謎中提取並輸出對應的單字。單字提取的路徑可以是水平、垂直或對角線。
解題思路
題目描述了四種可能的路徑：
- 從 (x1, y1) 到 (x2, y2) 的對角線 (x1-x2 == y1-y2)。
- 從 (x1, y1) 到 (x2, y2) 的水平線 (x1 == x2)。
- 從 (x1, y1) 到 (x2, y2) 的垂直線 (y1 == y2)。
- 從 (x1, y1) 到 (x2, y2) 的反對角線。
程式碼根據這四種情況，使用迴圈迭代字謎，並將對應的字元輸出。
複雜度分析
- 時間複雜度: O(max(h, w))，因為最壞情況下需要遍歷字謎的行或列。
- 空間複雜度: O(1)，程式只使用了常數級的額外空間。
程式碼
#include <iostream>
using namespace std;
int h,w,x1,y1,x2,y2;
char a[101][101];
int main(){
cin >> h >> w >> x1 >> y1 >> x2 >> y2;
for(int i=1;i<=h;++i)
for(int j=1;j<=w;++j)
cin >> a[i][j];
if(x1-x2==y1-y2)
for(int i=x1,j=y1;i<=x2;++i,++j)
cout << a[i][j];
else if(x1==x2)
for(int i=y1;i<=y2;++i)
cout << a[x1][i];
else if(y1==y2)
for(int i=x1;i<=x2;++i)
cout << a[i][y1];
else
for(int i=x1,j=y1;i<=x2;++i,--j)
cout << a[i][j];
}