P7663

max0810 · 2021-07-09 17:34:54 · 题解

思路还是比较简单的，完全没有蓝题的难度。

考虑bfs，每遇到一个点就往外广度搜索，去找最近的点。

时间看起来比较多，但到了后面有很多树，每个点的时间是非常快的，再加点优化，时间其实差不多是O(g)的。

具体请见代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
struct node
{
    int x,y;
}now,nex;
const int dir[4][2] = {0,-1,-1,0,0,1,1,0};
char a[505][505];
int r,s,g;
bool vis[505][505];
int f(int x1,int y1,int x2,int y2)//算距离 
{
    return (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1);
}
int bfs(int x,int y)//bfs模板不用多讲吧 
{
    memset(vis,0,sizeof vis);
    queue<node> que;
    int ans = 0x7ffffff;
    now.x = x;now.y = y;
    que.push(now);
    while(!que.empty())
    {
        now = que.front();
        que.pop();
        if(f(now.x,now.y,x,y)>ans)continue;//比最小值大就没必要枚举下去了（优化） 
        for(int i = 0;i < 4;i++)
        {
            int xx = now.x+dir[i][0];
            int yy = now.y+dir[i][1];
            if(xx<1||xx>r||yy<1||yy>s||vis[xx][yy])continue;
            vis[xx][yy] = 1;
            int s = f(xx,yy,x,y);
            if(s >= ans)continue;//同上 
            if(a[xx][yy] == 'x')ans = s;//注意只有是当前位置有苹果树才更新答案 
            nex.x = xx;nex.y = yy;
            que.push(nex);
        }
    }
    return ans;
}
int main()
{
//  freopen("jabuke.in","r",stdin);
//  freopen("jabuke.out","w",stdout);
    cin >> r >> s;
    for(int i = 1;i <= r;i++)
        for(int j = 1;j <= s;j++)
            cin >> a[i][j];
    cin >> g;
    while(g--)
    {
        int x,y;
        cin >> x >> y;
        if(a[x][y] == 'x')//如果这个点是x就直接输出0（优化） 
        {
            cout << "0\n";
            continue;
        }
        cout << bfs(x,y) << endl;
        a[x][y] = 'x';//一定要记得 
    }
    return 0;
}