2 条题解

  • 1
    @ 2025-6-12 22:02:02

    set,vector都可以 暂时存走了哪些点都可以都可 然后把走过的点赋值上ans if(jz[x][y]==0)判断走没走过优化避免重复计算值 其他的就是vector用法

    #include<bits/stdc++.h>
    #define ll long long 
    using namespace std;
    ll n,m,ans;
    char a[1005][1005];
    bool pd[1005][1005]; 
    ll jz[1005][1005];
    vector<pair<ll,ll>>b;
    void dfs(int x,int y,char syg)
    {
    	if(jz[x][y]!=0||pd[x][y]==true|| x<1||x>n|| y<1||y>n|| syg==a[x][y])
    		return;
    	pd[x][y]=true;
    	ans++;
      b.push_back(make_pair(x,y));
    	dfs(x+1,y,a[x][y]); 
    	dfs(x-1,y,a[x][y]); 
    	dfs(x,y+1,a[x][y]); 
    	dfs(x,y-1,a[x][y]);
    	return; 
    } 
    int main()
    {
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    	cin>>n>>m;;
    	for(int i=1;i<=n;i++)
    	   for(int j=1;j<=n;j++)
    		   cin>>a[i][j];
    	while(m--)
    	{
    		ll x,y;
    		cin>>x>>y;
    		if(jz[x][y]==0)
    		{
    		  dfs(x,y,'a');
          for (auto&i:b)
            jz[i.first][i.second]=ans;
          b.clear();
          ans=0;
    		}
    	  printf("%lld\n",jz[x][y]);
    	 } 
    	 return 0;
    }
    
    
    • @ 2025-6-12 22:14:32

      比并查集快,还见简单 orz

信息

ID
1095
时间
1000ms
内存
256MiB
难度
9
标签
递交数
58
已通过
4
上传者