Educational Codeforces Round 1 D. Igor In the Museum（BFS）

本文主要是介绍Educational Codeforces Round 1 D. Igor In the Museum（BFS），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接
题意：给你一个图，再给你几个点，然后问这个点能到达的*有几个。
解答：BFS，为了避免超时，我们BFS某一个点的时候，可以把这个点到达的’.’点编上序号，最后记下这个序号对应的能到达的墙数，这样我们读入一个点，如果已经算出，就不用再BFS了。

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define X first
#define Y second
#define cl(a,b) memset(a,b,sizeof(a))
typedef pair<int,int> P;
const int maxn=1005;
const int inf=1<<27;
#define mod 1000000007char a[maxn][maxn];int dir[][2]={1,0,0,1,-1,0,0,-1};
int vis[maxn][maxn];//标记的同时，编上BFS的序号
int num[100005];//记下序号对应的值
int n,m,k;
int tt;
void bfs(int x,int y){queue<P> q;q.push(P(x,y));//cl(vis,-1);vis[x][y]=tt;int ans=0;while(!q.empty()){P t=q.front();q.pop();for(int i=0;i<4;i++){int xx=t.X+dir[i][0];int yy=t.Y+dir[i][1];if(xx<0||xx>=n||yy<0||yy>=m||vis[xx][yy])continue;if(a[xx][yy]=='*'){ans++;continue;}q.push(P(xx,yy));vis[xx][yy]=tt;}}num[tt]=ans;
}
int main(){scanf("%d%d%d",&n,&m,&k);for(int i=0;i<n;i++){scanf("%s",a[i]);}tt=1;while(k--){int x,y;scanf("%d%d",&x,&y);x--;y--;if(vis[x][y]){printf("%d\n",num[vis[x][y]]);continue;}bfs(x,y);printf("%d\n",num[tt]);tt++;}return 0;
}

这篇关于Educational Codeforces Round 1 D. Igor In the Museum（BFS）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---