f257 - 君王的處刑遊戲
題目描述
題目描述了一個 n x n 的方陣，初始每個位置的驚恐值為 0。給定 k 個座標，表示 k 個囚犯被處決。每次處決一個囚犯，其周圍 (上下左右及對角線) 的囚犯驚恐值加 1。要求輸出處刑完成後，每個位置的驚恐值。如果某個位置的囚犯被處決，則輸出 'x'。
解題思路
這題的核心是模擬處刑過程。首先，建立一個 n x n 的二維陣列來儲存每個位置的驚恐值。然後，遍歷給定的 k 個座標，將這些位置標記為 'x' (表示被處決)。接著，對於每個被處決的囚犯，遍歷其周圍的 8 個位置，如果該位置沒有被處決，則將其驚恐值加 1。最後，遍歷整個陣列，輸出每個位置的驚恐值或 'x'。
複雜度分析
- 時間複雜度: O(n^2 * k)。其中 n 是方陣的大小，k 是被處決的囚犯數量。因為需要遍歷 k 個囚犯，並且對於每個囚犯，需要遍歷其周圍的最多 8 個位置。
- 空間複雜度: O(n^2)。需要一個 n x n 的二維陣列來儲存驚恐值。
程式碼
#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>
char a[101][101];
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(){
int n,t,x,y;
while(n=read()){
t=read();
for(int i=0;i<101;++i)
for(int j=0;j<101;++j)
a[i][j]=0;
while(t--){
y=read();
x=read();
a[x][y]=-1;
}
for(int ii=0;ii<n;++ii)
for(int jj=0;jj<n;++jj)
if(a[ii][jj]!=-1)
for(int i=-1;i<=1;++i)
for(int j=-1;j<=1;++j)
if(ii+i>=0&&jj+j>=0&&a[ii+i][jj+j]==-1)
++a[ii][jj];
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
if(a[i][j]==-1)
putchar_unlocked('x');
else
write(a[i][j]);
}
putchar_unlocked('\n');
}
}
}