1 solutions

  • 0
    @ 2025-11-27 11:59:47

    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

    Information

    ID
    135
    Time
    1000ms
    Memory
    128MiB
    Difficulty
    (None)
    Tags
    # Submissions
    0
    Accepted
    0
    Uploaded By