f148 - 2. 定向越野 (Orienteering)
題目描述
題目給定一個二維地圖，地圖由 '0' 和小寫字母組成。字母代表目標點，'0' 代表障礙物。題目要求找到前 t 個出現的目標點的座標，並按照目標點字母的順序輸出。如果目標點少於 t 個，則輸出 "Mission fail."。
解題思路
程式碼首先讀取地圖的尺寸 x 和 y，以及需要找到的目標點數量 t。然後，它遍歷地圖，將每個目標點的座標儲存在 ans 陣列中，其中 ans[i][0] 儲存第 i 個字母的行座標，ans[i][1] 儲存第 i 個字母的列座標。如果找到目標點，則將 a 變數加 1，表示已找到一個目標點。最後，程式碼檢查是否找到了至少 t 個目標點。如果找到了，則按照字母的順序輸出前 t 個目標點的座標。否則，輸出 "Mission fail."。
複雜度分析
- 時間複雜度: O(x * y)
- 空間複雜度: O(1)
程式碼
#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 <stdio.h>
int ans[26][2],x,y,t,a(0);
char n;
inline int read(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
inline void write(int x) {
if(x==0){
putchar_unlocked('0');
return;
}
int stk[9],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
int main(){
x=read();
y=read();
t=read();
for(int i(0);i<26;++i)
ans[i][0]=-1;
for(int i(0),j(0);i<x;++i,j=0){
for(;j<y;++j){
n=getchar_unlocked();
if(n!='0'){
n-=97;
ans[n][0]=i;
ans[n][1]=j;
++a;
}
n=getchar_unlocked();
}
}
if(a<t)
puts("Mission fail.");
else{
for(int i(0);t>0;++i){
if(ans[i][0]!=-1){
write(ans[i][0]);
putchar_unlocked(' ');
write(ans[i][1]);
putchar_unlocked('\n');
--t;
}
}
}
}