0分求助

P1141 01迷宫

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 怎么个预处理法


|