a746 - 画蛇添足
題目描述
題目描述一個畫蛇的故事，並要求根據給定的點座標，在一個 n x n 的網格中畫線，並用 * 標記被線覆蓋的格子，用空格標記未覆蓋的格子，最後輸出網格。線段只能平行於網格的邊。
解題思路
這題的核心是模擬畫線的過程。題目保證相鄰點之間的線段平行於網格邊，因此只需要考慮水平或垂直線段。對於每兩個相鄰點 (x1, y1) 和 (x2, y2)，如果 x1 == x2，則表示垂直線段，需要將 (x1, min(y1, y2)) 到 (x1, max(y1, y2)) 之間的格子標記為 *。如果 y1 == y2，則表示水平線段，需要將 (min(x1, x2), y1) 到 (max(x1, x2), y1) 之間的格子標記為 *。最後，按照題目要求的格式輸出網格。
複雜度分析
- 時間複雜度: O(n*m + n^2)，其中 n 是網格邊長，m 是點的數量。最壞情況下，需要遍歷所有點來畫線，並且需要遍歷整個網格來輸出。
- 空間複雜度: O(n^2)，用於儲存網格。
程式碼
#include <iostream>
using namespace std;
bool a[501][501];
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int m,n,x,y,x2,y2,tmp;
while(cin >> n >> m){
for(int i=0;i<501;++i)
for(int j=0;j<501;++j)
a[i][j]=0;
x2=-1;
while(m--){
cin >> x >> y;
y--;
x--;
if(x2!=-1){
if(x==x2){
tmp=max(y,y2);
for(int i=min(y,y2);i<=tmp;++i)
a[x][i]=1;
}
else{
tmp=max(x,x2);
for(int i=min(x,x2);i<=tmp;++i)
a[i][y]=1;
}
}
x2=x;
y2=y;
}
for(int i=0;i<=n+1;++i)
cout << "-";
cout << "\n";
for(int i=0;i<n;++i){
cout << "|";
for(int j=0;j<n;++j){
if(a[i][j]==1)
cout << "*";
else
cout << " ";
}
cout << "|\n";
}
for(int i=0;i<=n+1;++i)
cout << "-";
cout << "\n";
}
}