f170 - m5a1-尋找小狗(Dog)
題目描述
題目描述了一個在 N x N 地圖上尋找小狗的問題。小狗只能移動到與當前格子相鄰（上下左右）且海拔高度差距不超過 2 的格子。目標是計算小狗可能到達的格子數量。
解題思路
本題可以使用廣度優先搜尋 (BFS) 演算法來解決。將地圖視為一個圖，每個格子是一個節點，相鄰且海拔高度差距不超過 2 的格子之間存在邊。從小狗的起始位置開始，使用 BFS 遍歷所有可到達的格子，並計算到達的格子數量。使用 used 陣列記錄已訪問的格子，避免重複訪問。
複雜度分析
- 時間複雜度: O(N^2)，其中 N 是地圖的邊長。因為最壞情況下，BFS 需要遍歷所有格子。
- 空間複雜度: O(N^2)，主要用於儲存
used陣列和佇列q。在最壞情況下，佇列可能包含所有格子。
程式碼
#include <iostream>
#include <cmath>
#include <queue>
using namespace std;
int a[1001][1001],x,y,ans;
bool used[1001][1001];
queue < pair<int,int> > q;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int n;
cin >> n;
cin >> x >> y;
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
cin >> a[i][j];
}
}
pair<int,int> p(x,y);
used[x][y]=1;
ans=1;
q.push(p);
while(q.empty()==0){
pair<int,int> tmp = q.front();
q.pop();
x = tmp.first;
y = tmp.second;
//cout << x << " " << y << " " << a[x][y] << "\n";
int d = a[x][y];
if(x>0&&used[x-1][y]==0&&abs(a[x-1][y]-d)<3){
++ans;
pair<int,int> tmp2(x-1,y);
used[x-1][y]=1;
q.push(tmp2);
}
if(x<n-1&&used[x+1][y]==0&&abs(a[x+1][y]-d)<3){
++ans;
pair<int,int> tmp2(x+1,y);
used[x+1][y]=1;
q.push(tmp2);
}
if(y>0&&used[x][y-1]==0&&abs(a[x][y-1]-d)<3){
++ans;
pair<int,int> tmp2(x,y-1);
used[x][y-1]=1;
q.push(tmp2);
}
if(y<n-1&&used[x][y+1]==0&&abs(a[x][y+1]-d)<3){
++ans;
pair<int,int> tmp2(x,y+1);
used[x][y+1]=1;
q.push(tmp2);
}
}
cout << ans;
}