题意:
给出一个地图,符号.代表空地,可走,*代表墙,不可走,墙的每一面都有一幅画,问给定一个空地,可以看到多少画
做法:
使用两次BFS,第一次用于统计一个联通的子块最多可以看多少画,第二个BFS用于把这个联通块内的点都修改成答案.
注意一点技巧:每一次寻找不同的联通块,可以打上它的专属标记,以免一个墙只能被统计一次的情况出现
点击查看代码
// Problem: D. Igor In the Museum
// Contest: Codeforces - Educational Codeforces Round 1
// URL: https://codeforces.com/contest/598/problem/D
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// Author: a2954898606
// Create Time:2023-11-29 14:05:41
//
// Powered by CP Editor (https://cpeditor.org)
/*
/\_/\
(o o)
/ \
// ^ ^ \\
/// \\\
\ |
\_____/
/\_ _/\
*/
#include<bits/stdc++.h>
#define all(X) (X).begin(),(X).end()
#define all2(X) (X).begin()+1,(X).end()
#define pb push_back
#define mp make_pair
#define sz(X) (int)(X).size()
#define YES cout<<"YES"<<endl
#define Yes cout<<"Yes"<<endl
#define NO cout<<"NO"<<endl
#define No cout<<"No"<<endl
using namespace std;
typedef long long unt;
typedef vector<long long> vt_unt;
typedef vector<int> vt_int;
typedef vector<char> vt_char;
template<typename T1,typename T2> inline bool ckmin(T1 &a,T2 b){
if(a>b){
a=b;
return true;
}
return false;
}
template<typename T1,typename T2> inline bool ckmax(T1 &a,T2 b){
if(a<b){
a=b;
return true;
}
return false;
}
namespace smart_math{
long long quickpow(long long a,long long b,long long mod=0){
long long ret=1;
while(b){
if(b&1)ret*=a;
if(mod)ret%=mod;
b>>=1;
a*=a;
if(mod)a%=mod;
}
if(mod)ret%=mod;
return ret;
}
long long quickmul(long long a,long long b,long long mod=0){
long long ret=0;
while(b){
if(b&1)ret+=a;
if(mod)ret%=mod;
b>>=1;
a=a+a;
if(mod)a%=mod;
}
if(mod)ret%=mod;
return ret;
}
long long ceil_x(long long a,long long b){
if(a%b==0)return a/b;
else return (a/b)+1;
}
}
using namespace smart_math;
const long long mod=1e9+7;
const long long N=310000;
const long long M=300;
#define int long long
vector<vector<int> >a(1010,vector<int>(1011));
vector<vector<int> >vis(1010,vector<int>(1010));
int bfs1(int sx,int sy,int f){
queue<pair<int,int> >que;
que.push(mp(sx,sy));
vis[sx][sy]=f;
int cnt=0;
while(!que.empty()){
int nx=que.front().first;
int ny=que.front().second;
que.pop();
//cout<<"sx,sy,nx,ny"<<sx<<" "<<sy<<" "<<nx<<" "<<ny<<endl;
if(a[nx][ny-1]==-1){
cnt++;
//vis[nx][ny-1]=f;
}
if(a[nx][ny+1]==-1){
cnt++;
//vis[nx][ny+1]=f;
}
if(a[nx-1][ny]==-1){
cnt++;
//vis[nx-1][ny]=f;
}
if(a[nx+1][ny]==-1){
cnt++;
//is[nx+1][ny]=f;
}
//cout<<"judge:cnt"<<cnt<<endl;
for(int i=nx-1;i<=nx+1;i++){
for(int j=ny-1;j<=ny+1;j++){
int d=abs(i-nx)+abs(j-ny);
if(d>=2)continue;
if(a[i][j]==-1)continue;
if(vis[i][j]==f)continue;
// cnt++;
vis[i][j]=f;
que.push(mp(i,j));
}
}
}
return cnt;
}
void bfs2(int sx,int sy,int cnt,int f){
queue<pair<int,int> >que;
que.push(mp(sx,sy));
vis[sx][sy]=f;
a[sx][sy]=cnt;
while(!que.empty()){
int nx=que.front().first;
int ny=que.front().second;
que.pop();
for(int i=nx-1;i<=nx+1;i++){
for(int j=ny-1;j<=ny+1;j++){
int d=abs(i-nx)+abs(j-ny);
if(d>=2)continue;
if(a[i][j]==-1)continue;
if(vis[i][j]==f)continue;
a[i][j]=cnt;
vis[i][j]=f;
que.push(mp(i,j));
}
}
}
return;
}
int solve(){
int n,m,k;
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
a[i][0]=a[i][m+1]=-1;
}
for(int i=1;i<=m;i++){
a[0][i]=a[n+1][i]=-1;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char c;
cin>>c;
if(c=='*')a[i][j]=-1;
else a[i][j]=1;
}
}
int f=2;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]!=1)continue;
if(a[i][j]==-1)continue;
f+=3;
int cnt=bfs1(i,j,f);
bfs2(i,j,cnt,f+1);
}
}
for(int i=1;i<=k;i++){
int x,y;
cin>>x>>y;
cout<<a[x][y]<<endl;
}
return 0;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
t=1;
//cin>>t;
while(t--){
int flag=solve();
if(flag==1) YES;
if(flag==-1) NO;
}
return 0;
}