70pts求救

P1141 01迷宫

nannangua @ 2024-07-22 16:44:27

全都是TLE的点

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int maxn=1e3+3;
char a[maxn][maxn];
int vis[maxn][maxn],ans=0;
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
int n,T;
bool check(int x,int y)
{
    return x<=n && x>=1 && y<=n && y>=1;
}
void dfs(int x,int y)
{
    ans++;
    vis[x][y]=1;
    for(int i=0;i<4;i++)
    {
        int tx=x+dx[i];
        int ty=y+dy[i];
        if(check(tx,ty) && vis[tx][ty]==0)
        {
            if((a[x][y]=='1' && a[tx][ty]=='0') || (a[x][y]=='0' && a[tx][ty]=='1')) dfs(tx,ty);
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>T;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>a[i][j];
        }
    }
    int a,b;
    while(T--)
    {
        ans=0;
        memset(vis,0,sizeof(vis));
        cin>>a>>b;
        dfs(a,b);
        cout<<ans<<endl;
    }
    return 0;
}

by king_t @ 2024-07-22 16:53:01

时间复杂度的问题,定义ans[i][j]表示(i,j)能到达的点数,在dfs的时候处理经过的点的ans值, 在查询时如果ans已经被算出来直接输出,时间复杂度n2


by luca66 @ 2024-07-22 16:54:49

6这么牛逼的吗


by nannangua @ 2024-07-22 17:31:07

@king_t
是这样吗?eee好像还是不行

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int maxn=1e3+3;
char a[maxn][maxn];
int vis[maxn][maxn],ans=0,cnt[maxn][maxn];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
int n,T,c[maxn][maxn];
bool check(int x,int y)
{
    return x<=n && x>=1 && y<=n && y>=1;
}
void dfs(int x,int y)
{
    ans++;
    vis[x][y]=1;
    for(int i=0;i<4;i++)
    {
        int tx=x+dx[i];
        int ty=y+dy[i];
        if(check(tx,ty) && vis[tx][ty]==0)
        {
            if((a[x][y]=='1' && a[tx][ty]=='0') || (a[x][y]=='0' && a[tx][ty]=='1')) 
            {
                dfs(tx,ty);
                cnt[tx][ty]=ans;
            }
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>T;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>a[i][j];
        }
    }
    int a,b,c;
    memset(cnt,0,sizeof(cnt));
    while(T--)
    {
        ans=0;
        memset(vis,0,sizeof(vis));
        cin>>a>>b;  
        if(cnt[a][b]!=0) 
        {
            cout<<cnt[a][b]<<endl;
            continue;
        }    
        dfs(a,b);
        c=ans;
        cout<<ans<<endl;    
    }
    return 0;
}

by king_t @ 2024-07-22 18:58:58

抱歉刚才在吃饭没看见喵

又细看了一遍代码

这个代码没法AC首先是cnt数组算的不对,每次的cnt数组只储存了每次已经走过的格子数,如果路径有分支的话cnt数组就错了,这个可以再写一个dfs函数将cnt统一赋值(抱歉刚才没讲明白)

然后memset的时间复杂度是比较大的,因为每个点只会被访问一遍,所以vis数组可以不用memset

最后就是

char a[maxn][maxn];
int a,b,c;

定义了两个a,修改过之后就可以AC了

AC代码

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int maxn=1e3+3;
char a[maxn][maxn];
int vis[maxn][maxn],ans=0,cnt[maxn][maxn];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int n,T,c[maxn][maxn];
bool check(int x,int y)
{
    return x<=n && x>=1 && y<=n && y>=1;
}
void dfs1(int x,int y)//原dfs函数 
{
    ans++;
    vis[x][y]=1;
    for(int i=0;i<4;i++)
    {
        int tx=x+dx[i];
        int ty=y+dy[i];
        if(check(tx,ty) && vis[tx][ty]==0)
        {
            if((a[x][y]=='1' && a[tx][ty]=='0') || (a[x][y]=='0' && a[tx][ty]=='1')) 
            {
                dfs1(tx,ty);
            }
        }
    }
}
void dfs2(int x,int y)//赋值cnt数组 
{
    vis[x][y]=0;//这里用vis==0代表已访问,这样不用memset
    for(int i=0;i<4;i++)
    {
        int tx=x+dx[i];
        int ty=y+dy[i];
        if(check(tx,ty) && vis[tx][ty]==1)//同样的这里要用vis==1来判断
        {
            if((a[x][y]=='1' && a[tx][ty]=='0') || (a[x][y]=='0' && a[tx][ty]=='1')) 
            {
                cnt[tx][ty]=ans;
                dfs2(tx,ty);
            }
        }
    }
} 
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>T;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>a[i][j];
        }
    }
    int u,v;//改成了u和v
    while(T--)
    {
        ans=0;
        cin>>u>>v;  
        if(cnt[u][v]!=0) 
        {
            cout<<cnt[u][v]<<endl;
            continue;
        }
        dfs1(u,v);
        cout<<ans<<endl;
        dfs2(u,v);  
    }
    return 0;
}

by nannangua @ 2024-07-22 21:38:32

谢谢大佬@king_t


|