e167 - 演唱會記行 - 排隊買周邊
題目描述
題目描述了演唱會現場購買周邊的排隊情況。地圖上用 0 表示空地，1 表示排隊人潮。題目要求找到隊伍的最後尾座標。隊伍可能不連續，但最後尾一定在附近或附近的附近（定義如題目所述）。
解題思路
這題可以將地圖視為一個圖，排隊人潮（1）表示圖中的節點。相鄰的排隊人潮之間可以連線。題目要求找到隊伍的最後尾，也就是從結帳口座標出發，尋找與結帳口相鄰或相鄰的相鄰的排隊人潮。
程式碼使用廣度優先搜尋 (BFS) 來尋找隊伍的最後尾。從結帳口座標開始，不斷向周圍擴散，直到找到一個沒有其他相鄰排隊人潮的節點，這個節點就是隊伍的最後尾。
複雜度分析
- 時間複雜度: O(n*m)，其中 n 和 m 是地圖的長寬。因為 BFS 最多會遍歷整個地圖。
- 空間複雜度: O(n*m)，因為
p陣列儲存了地圖的資訊，並且在 BFS 的過程中，可能需要儲存所有排隊人潮的座標。
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <iostream>
using namespace std;
bool p[102][102];
int ansx,ansy;
inline void bfs(int x,int y){
p[x][y]=0;
for(int i(-1);i<=1;++i){
for(int j(-1);j<=1;++j){
if(x+i>=0&&y+j>=0&&p[x+i][y+j]){
bfs(x+i,y+j);
return;
}
}
}
for(int i(-2);i<=2;++i){
for(int j(-2);j<=2;++j){
if(x+i>=0&&y+j>=0&&p[x+i][y+j]){
bfs(x+i,y+j);
return;
}
}
}
ansx=x,ansy=y;
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int x,y;
while(cin >> x >> y){
if(x==0)return 0;
for(int i(0);i<x;++i)
for(int j(0);j<y;++j)
cin >> p[i][j];
cin >> x >> y;
bfs(x,y);
cout << ansx << " " << ansy << "\n";
}
}