题解:
一看到3000的范围,如果每次都进行暴力深搜的话,会不会超时?(应该会)
我们可以发现假设我们能从点(x1,y1)走到点(x2,y2)那么我们必然可以从(x2,y2)走到点(x1,y1)
那么假设我们走过这一片区域的面积是5,那么这五点,你从哪个点进入这个地图,最多能走出的面积也只能是5.
那就好办了,记忆化搜索。
我们把每个区域都标记为一种颜色,如果遇到我们之前标记的这个颜色,我们就可以直接输出之前这个颜色对应的面积了。
代码:
/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
const int maxn = 3010;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 1e9+7;
using namespace std;
int n,m,q;
char a[maxn][maxn];
int color[maxn][maxn];
bool visited[maxn][maxn];
int cnt[9000000];
int sum,ans=1;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
inline bool judge(int x,int y,int x1,int y1){
if(a[x][y]=='+'&&a[x1][y1]=='-'&&visited[x1][y1]==false) return true;
if(a[x][y]=='-'&&a[x1][y1]=='+'&&visited[x1][y1]==false) return true;
return false;
}
void dfs(int x,int y,int k){
color[x][y]=k;
sum++;
for(int i=0;i<4;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if(judge(x,y,nx,ny)){
visited[nx][ny]=true;
dfs(nx,ny,k);
}
}
}
int main()
{
cin>>n>>m>>q;
memset(a,-1,sizeof(a));
memset(visited,false,sizeof(visited));
for(int i=1;i<=n;i++){
scanf("%s",a[i]+1);
}
while(q--){
int x,y;
scanf("%d%d",&x,&y);
if(color[x][y]){
printf("%d\n",cnt[color[x][y]]);
}
else{
sum=0;
visited[x][y]=true;
dfs(x,y,ans);
cnt[ans++]=sum;
printf("%d\n",sum);
}
}
return 0;
}

京公网安备 11010502036488号