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