2014.计算机2.Problem C. 图像识别

谁践踏了优雅 2023-07-18 06:24 8阅读 0赞

**题目描述**  
在图像识别中，我们经常需要分析特定图像中的一些特征，而其中很重要的一点就是识别出图像的多个区域。在这个问题中，我们将给定一幅N x M的图像，其中每个1 x 1的点都用一个\[0,255\]的值来表示他的RGB颜色。如果两个相邻的像素点颜色差不超过D，我们就认为这两个像素点属于同一个区域。对于一个像素点(x,y) ，以下这8个点（如果存在）是与它相邻的：（x-1, y-1），（x-1,y），（x-1,y+1），（x,y-1），（x,y+1），（x+1,y-1），（x+1,y），（x+1,y+1）。  
你的任务是写一个程序，分辨出给定图像中一共被分为多少个区域。

**输入格式**  
输入数据包含多组测试数据。  
输入的第一行是一个整数T（T<=100），表示测试数据的组数。  
每组测试数据的第一行是三个整数N,M,D（1<=N,M<=100, 0<=D<=255），意义如上所述。  
接下来N行，每行M个整数，表示给定图像的每个像素点颜色。

**输出格式**  
对于每组测试数据输出一行，即图像中的区域数量。

**输入样例**

2
    3 3 0
    1 1 1
    0 1 0
    0 1 0
    3 4 1
    10 11 12 13
    9 8 7 6
    2 3 4 5

**输出样例**

3
    1

#include<bits/stdc++.h>
    using namespace std;
    int data[105][105];
    int vis[105][105];
    int m,n,d;
    int dir[8][2]={ { -1,-1},{ -1,0},{ -1,1},{ 0,-1},{ 0,1},{ 1,-1},{ 1,0},{ 1,1}};
    void check(int x,int y){ 
    	int dx,dy;
    	for(int i=0;i<8;i++){ 
    		dx=x+dir[i][0];
    		dy=y+dir[i][1];
    		if(dx>=0&&dx<n&&dy>=0&&dy<m&&vis[dx][dy]==0&&abs(data[dx][dy]-data[x][y])<=d){ 
    			vis[dx][dy]=1;
    			check(dx,dy);
    		}
    	}
    	return;
    }
    int main() { 
    	int T;
    	cin>>T;
    	while(T--) { 
    		int cnt=0;
    		cin>>n>>m>>d;
    		memset(vis,0,sizeof(vis));
    		for(int i=0; i<n; i++) {  //n X m
    			for(int j=0; j<m; j++) { 
    				cin>>data[i][j];
    			}
    		}
    		for(int i=0; i<n; i++) {  //n X m
    			for(int j=0; j<m; j++) { 
    				if(vis[i][j]==0) { 
    					vis[i][j]=1;
    					check(i,j);
    					cnt++;	
    				}
    			}
    		}
    		cout<<cnt<<endl;
    	}
    	return 0;
    }