A rectangular map consisting of N rows and M columns of square areas is given. Each area is painted with a certain color. Two areas on the map belong to the same country if the following conditions are met: The map can be described by a zero-indexed matrix A consisting of N rows and M columns of integers. The color of each area is described by the corresponding element of the matrix. Two areas have the same color if and only if their corresponding matrix elements have the same value. For example, consider the following matrix A consisting of seven rows and three columns: A[0][0] = 5 A[0][1] = 4 A[0][2] = 4 A[1][0] = 4 A[1][1] = 3 A[1][2] = 4 A[2][0] = 3 A[2][1] = 2 A[2][2] = 4 A[3][0] = 2 A[3][1] = 2 A[3][2] = 2 A[4][0] = 3 A[4][1] = 3 A[4][2] = 4 A[5][0] = 1 A[5][1] = 4 A[5][2] = 4 A[6][0] = 4 A[6][1] = 1 A[6][2] = 1 Matrix A describes a map that is colored with five colors. The areas on the map belong to eleven different countries (C1−C11), as shown in the following figure: Write a function that, given a zero-indexed matrix A consisting of N rows and M columns of integers, returns the number of different countries to which the areas of the map described by matrix A belong. For example, given matrix A consisting of seven rows and three columns corresponding to the example above, the function should return 11
Answers
Answer:
Explanation:
void checkNeighbor(const vector<vector<int> > &A, vector<vector<int> > &B, int i,int j, int N, int M)
{
if(B[i][j] == -1) return;
B[i][j] = -1;
if(i+1 < N)
if(A[i+1][j] == A[i][j]) checkNeighbor(A, B, i+1, j, N, M);
if(i-1 >= 0)
if(A[i-1][j] == A[i][j]) checkNeighbor(A, B, i-1, j, N, M);
if(j+1 < M)
if(A[i][j+1] == A[i][j]) checkNeighbor(A, B, i, j+1, N, M);
if(j-1 >= 0)
if(A[i][j-1] == A[i][j]) checkNeighbor(A, B, i, j-1, N, M);
}
int countries_count(const vector< vector<int> > &A) {
if (A.empty()) return 0;
int sum = 0;
int N = A.size();
int M = A[0].size(); // N*M
if (N ==0 || M==0) return 0;
vector<vector<int> > B(A);
for(int i=0; i<N; i++)
for(int j = 0; j<M; j++) {
if (B[i][j] >= 0) {
cout << i<< j << endl;
checkNeighbor(A, B, i, j, N, M);
sum ++;
}
}
return sum;
}
On Mon, Feb 4, 2013 at 2:19 PM, Yunxing Dai <[email protected]> wrote:
def color (val, B, A, x, y):
if x < 0 or x >= len(A):
return
if y < 0 or y >= len(A[0]):
return
if not B[x][y] :
return
if A[x][y] != val:
return
B[x][y] = False
color(val, B, A, x + 1, y)
color(val, B, A, x - 1, y)
color(val, B, A, x, y - 1)
color(val, B, A, x, y + 1)
def countries_count( A ):
B = [[True for x in A[0]] for y in A]
count = 0
for x in xrange(0, len(A)):
for y in xrange(0, len(A[x])):
if not B[x][y]:
continue;
count += 1
color(A[x][y], B, A, x, y)
return count
On Mon, Feb 4, 2013 at 2:18 PM, Yunxing Dai <[email protected]> wrote:
> A rectangular map consisting of N rows and M columns of square areas
> is given. Each area is painted with a certain color.
>
> Two areas on the map belong to the same country if the following
> conditions are met:
>
> they have the same color;
> it is possible to travel from one area to the other by moving only
> north, south, west or east without moving over areas of a different
> color.
>
> The map can be described by a zero-indexed matrix consisting of N rows
> and M columns of integers. The color of each area is described by the
> corresponding element of the matrix. Two areas have the same color if
> and only if their corresponding matrix elements have the same value.
>
> For example, consider the following matrix A consisting of seven rows
> and three columns:
>
> A[0][0] = 5 A[0][1] = 4 A[0][2] = 4
> A[1][0] = 4 A[1][1] = 3 A[1][2] = 4
> A[2][0] = 3 A[2][1] = 2 A[2][2] = 4
> A[3][0] = 2 A[3][1] = 2 A[3][2] = 2
> A[4][0] = 3 A[4][1] = 3 A[4][2] = 4
> A[5][0] = 1 A[5][1] = 4 A[5][2] = 4
> A[6][0] = 4 A[6][1] = 1 A[6][2] = 1
>
> Matrix A describes a map that is colored with five colors. Areas on
> the map belong to eleven different countries:
>
> area A[0][0] forms a one-area country;
> areas A[0][1], A[0][2], A[1][2], A[2][2] belong to the same country;
> area A[1][0] forms a one-area country;
> area A[1][1] forms a one-area country;
> area A[2][0] forms a one-area country;
> areas A[2][1], A[3][0], A[3][1], A[3][2] belong to the same country;
> areas A[4][0], A[4][1] belong to the same country;
> areas A[4][2], A[5][1], A[5][2] belong to the same country;
> area A[5][0] forms a one-area country;
> area A[6][0] forms a one-area country;
> areas A[6][1], A[6][2] belong to the same country.
>
> Write a function
>
> int countries_count(const vector< vector<int> > &A);
>
> that, given a zero-indexed matrix A consisting of N rows and M columns
> of integers, returns the number of different countries that the areas
> of the map described by matrix A belong to.
>
> Assume that:
>
> N is an integer within the range [1..1,000,000];
> M is an integer within the range [1..1,000,000];
> the number of elements in matrix A is within the range [1..1,000,000];
> each element of matrix A is an integer within the range
> [-1,000,000,000..1,000,000,000].
>
> For example, given matrix A consisting of seven rows and three columns
> corresponding to the example above, the function should return 11.
>
> Complexity:
>
> expected worst-case time complexity is O(N*M);
> expected worst-case space complexity is O(N*M).
>
>
> --
> Best Regards,
>
> Huang Xinyun 黄昕昀
> Mobile: +86 13901898800
> Email: [email protected]
>
> All things come to those who wait.苍天不负有心人。
>
>
>
> --
> Happy Hacking!
>
> Yunxing Dai
--
Happy Hacking!
Yunxing Dai
--
You received this message because you are subscribed to the Google Groups "csjobseekers" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [email protected].
For more options, visit https://groups.google.com/groups/opt_out.