P7663 [COCI 2014/2015 #5] JABUKE题目描述给你一个n × m n \times mn×m的矩阵其中苹果树用x表示空地用.表示。有g gg年每年都会从天而降一个苹果落在坐标( x i , y i ) (x_i,y_i)(xi​,yi​)上要求出这个苹果离最近一棵苹果树的距离的平方。当然一年后这个苹果会长成新的一颗苹果树并参与一年后落下的那个苹果的计算。输入格式第一行两个正整数n , m n,mn,m表示矩阵的长宽。接下来n nn行每行m mm个字符字符仅含x和.表示该矩阵。接下来一个正整数g gg表示年份。接下来g gg行每行两个正整数x i , y i x_i,y_ixi​,yi​表示每年苹果下落的位置。输出格式一共g gg行每行一个整数表示每个苹果下落时离最近一棵苹果树的距离的平方。输入输出样例 #1输入 #13 3 x.. ... ... 3 1 3 1 1 3 2输出 #14 0 5输入输出样例 #2输入 #25 5 ..x.. ....x ..... ..... ..... 4 3 1 5 3 4 5 3 5输出 #28 8 4 1说明/提示对于30 % 30\%30%的数据1 ≤ g ≤ 500 1 \leq g \leq 5001≤g≤500。对于100 % 100\%100%的数据1 ≤ n , m ≤ 500 , 1 ≤ g ≤ 10 5 1\leq n,m \leq 500,1 \leq g \leq 10^51≤n,m≤500,1≤g≤105保证初始矩阵至少包含一棵苹果树。距离计算公式d ( ( x 1 , y 1 ) , ( x 2 , y 2 ) ) ( x 1 − x 2 ) 2 ( y 1 − y 2 ) 2 d((x_1,y_1),(x_2,y_2))\sqrt{(x_1-x_2)^2(y_1-y_2)^2}d((x1​,y1​),(x2​,y2​))(x1​−x2​)2(y1​−y2​)2​。译自 COCI 2014/2015 CONTEST #5。C实现#includebits/stdc.husingnamespacestd;setintst[510];intn,m,g,d;charmp[510][510];signedmain(){ios::sync_with_stdio(0);cinnm;for(inti1;in;i){st[i].insert(-1e4);st[i].insert(1e4);for(intj1;jm;j){cinmp[i][j];if(mp[i][j]x)st[i].insert(j);}}cing;if(n*g5e7)d20;elsed130;for(inti1;ig;i){intx,y,minl1e9;cinxy;for(intjmax(1,x-d);jmin(n,xd);j){intl*(--st[j].upper_bound(y)),r*st[j].lower_bound(y);minlmin(minl,(x-j)*(x-j)(y-l)*(y-l));minlmin(minl,(x-j)*(x-j)(y-r)*(y-r));}coutminl\n;st[x].insert(y);}}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容