一道水广搜题 这个liantong数组就是用来记忆化的,但是即便这样还是TLE了两个点,这玩意还有啥剪枝的方法了吗
#include<bits/stdc++.h>
const int N=1005;
using namespace std;
int n,m;
bool mapp[N][N];
int vis[N][N];
int liantong[N][N];
int startx,starty;
int ans;
struct node
{
int x;
int y;
}now,endd;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
void bfs(int x,int y)
{
queue <node> q;
now.x=x;
now.y=y;
q.push(now);
while(!q.empty())
{
now=q.front();
q.pop();
for(int i=0;i<4;i++)
{
endd.x=now.x+dx[i];
endd.y=now.y+dy[i];
if(endd.x>=1 && endd.x<=n && endd.y>=1 && endd.y<=n && !vis[endd.x][endd.y] && mapp[endd.x][endd.y]==!mapp[now.x][now.y])
{
vis[endd.x][endd.y]=1;
ans++;
q.push(endd);
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%1d",&mapp[i][j]);
memset(liantong,-1,sizeof liantong);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&startx,&starty);
if(liantong[startx][starty]!=-1)
{
cout<<liantong[startx][starty]<<endl;
continue;
}
memset(vis,0,sizeof vis);
vis[startx][starty]=1;
ans=1;
bfs(startx,starty);
printf("%d\n",ans);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(vis[i][j]) liantong[i][j]=ans;
}
}