ikuncdl @ 2024-10-05 21:32:50
大佬们帮忙看看用的二维深搜
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<map>
#include<queue>
#include<stack>
using namespace std;
int n,m,c;
char f[1005][1005];
bool v[1005][1005];
int dx[] = {0,0,0,-1,1};
int dy[] = {0,1,-1,0,0};
void r(int x,int y)
{
for (int i = 1;i <= 4;i++)
{
int nx = x + dx[i],ny = y + dy[i];
if (nx < 1 || nx > n || ny < 1 || ny > n)
{
continue;
}
if (f[x][y] == f[nx][ny])
{
continue;
}
if (v[nx][ny])
{
continue;
}
c++;
v[nx][ny] = true;
r(nx,ny);
}
}
int main()
{
cin>>n>>m;
for (int i = 1;i <= n;i++)
{
for (int j = 1;j <= n;j++)
{
cin>>f[i][j];
}
}
for (int i = 1;i <= m;i++)
{
int fi,fj;
c = 0;
cin>>fi>>fj;
r(fi,fj);
for (int j = 1;j <= n;j++)
{
memset(v[j],0,sizeof(v[j]));
}
cout<<c;
}
return 0;
}
by ikuncdl @ 2024-10-05 21:34:28
补充一下#3#10#11#1是TLE其他全WA样例过了
by AC_CJQ @ 2024-10-05 21:38:20
可以试着预处理,因为是TLE
by AC_CJQ @ 2024-10-05 21:41:13
做法是没问题的,但时间会爆(O(n*m)),所以在开始预处理,把每次搜的都存一下就OK了
(蒟蒻一只,有错欢迎指出)
by ikuncdl @ 2024-10-13 12:09:59
@AC_CJQ 怎么个预处理法