125. Objects Count

Problem Statement:
In computer vision, the problem of counting objects in an image has been studied a long time ago; a very naïve approach has been developed for counting the objects in a gray scale image (in which each pixel has a value between [0,255]). Experiments have shown that this simple algorithm has yielded some good results.
The algorithm start by scanning the image pixel by pixel (from top left to bottom right) and assign an intensity value vi for each pixel. The intensity value v is one of a small list of given values V = {v1, v2, ... , vn} where 0 < vi < 255, each pixel will be mapped to exactly one intensity value that is the closest to the pixel's value itself (in case of tie the smallest intensity value is taken). A reasonable assumption at this point is "a region of at least b adjacent pixels (where each pixel has at most 4 adjacent pixels up, down, left, and right) sharing the same intensity value represents one object in the image".

Input Format:
The first line contains one integer 0 < t ≤ 100 which is the number of test cases. Each test case is a given gray scale image, the first line contains two integers 0 < n,m ≤ 128 To denote the image dimensions, each of the following n lines contains m values each of which denote the pixel value at that position (each pixel value is in the range [0,255] inclusively), the next line contains one integer 0 < V < 255 to denote the size the list of intensity values), the next line contains V values as the intensity values, the next line contains an integer 0 < b < 50 to denote the minimum bound of adjacent pixels to be considered as an object.

Output Format:
For each test case you have to output one line containing the number of objects in the given image described by the test case.

Sample Input:
2 5 5 28 34 12 11 100 35 30 10 12 110 230 34 36 120 130 233 218 233 218 233 240 233 218 233 218 8 16 40 64 90 128 150 190 230 5 4 3 28 34 12 35 30 10 230 34 36 233 218 233 4 32 96 160 224 2

Sample Output:
2 2

 Added by: samiemad Added at: 2014-02-26 01:15:05 UTC Time Limit: 3 seconds Partial score: No Source: ACM Syrian Collegiate Programming Contest 2013