打卡信奥刷题（3146）用C++实现信奥题 P7663 [COCI 2014/2015 #5] JABUKE

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

输入 #1

3 3 x.. ... ... 3 1 3 1 1 3 2

输出 #1

4 0 5

输入输出样例 #2

输入 #2

5 5 ..x.. ....x ..... ..... ..... 4 3 1 5 3 4 5 3 5

输出 #2

8 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++实现

#include<bits/stdc++.h>usingnamespacestd;set<int>st[510];intn,m,g,d;charmp[510][510];signedmain(){ios::sync_with_stdio(0);cin>>n>>m;for(inti=1;i<=n;i++){st[i].insert(-1e4);st[i].insert(1e4);for(intj=1;j<=m;j++){cin>>mp[i][j];if(mp[i][j]=='x')st[i].insert(j);}}cin>>g;if(n*g==5e7)d=20;elsed=130;for(inti=1;i<=g;i++){intx,y,minl=1e9;cin>>x>>y;for(intj=max(1,x-d);j<=min(n,x+d);j++){intl=*(--st[j].upper_bound(y)),r=*st[j].lower_bound(y);minl=min(minl,(x-j)*(x-j)+(y-l)*(y-l));minl=min(minl,(x-j)*(x-j)+(y-r)*(y-r));}cout<<minl<<"\n";st[x].insert(y);}}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容