1 条题解

  • 0
    @ 2025-11-3 0:09:35

    C++ :

    #include <bits/stdc++.h>
    #define umap unordered_map
    using namespace std;
    typedef long long ll;
    
    int n ,m;
    const int N = 510;
    int a[N][N];
    int vis[N][N];
    umap<string ,int> mp;
    
    //方向数组 
    int dx[] = {1 ,0 ,-1 ,0};
    int dy[] = {0 ,1 ,0 ,-1};
    
    void dfs(int x ,int y ,string &s/*&s:取s的地址,可以在函数里直接修改*/)
    {
    	for (int i = 0;i < 4;i++)
    	{
    		int nx = x + dx[i];
    		int ny = y + dy[i];
    		
    		if (nx >= 1 && nx <= n && ny >= 1 && ny <= m) //越界判断 
    		{
    			if (vis[nx][ny] || a[nx][ny] != a[x][y]) continue; //访问过或者颜色不一可以直接跳过 
    			s += char(i + '0'); 
    			vis[nx][ny] = 1; //标记 
    			dfs(nx ,ny ,s);
    			//不用回溯,因为不会再次访问 
    		}
    	}
    	s += ' '; //注意:最后要加一个空格,因为转弯地点会发生改变,加空格为了区分不同的转弯地点 
    }
    
    int main()
    {
    	scanf("%d%d",&n ,&m);
    	
    	for (int i = 1;i <= n;i++)
    	{
    		for (int j = 1;j <= m;j++)
    		{
    			scanf("%d",&a[i][j]);
    		}
    	}
    	
    	int ans = 0;
    	for (int i = 1;i <= n;i++)
    	{
    		for (int j = 1;j <= m;j++)
    		{
    			if (!vis[i][j]) //没被走过就走 
    			{
    				vis[i][j] = 1;
    				
    				string s = "";
    				dfs(i ,j ,s);
    				
    				if (!mp[s]) //如果没有这种方块就加一个种类 
    				{
    					ans++;
    				}
    				mp[s] = 1; //标记 
    			}
    		}
    	}
    	
    	printf("%d\n",ans);
    	
    	return 0;
    }
    
    
    • 1

    信息

    ID
    5630
    时间
    1000ms
    内存
    128MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者