Read problems statements in Russian and Vietnamese as well. 
Chef and Hasan went for skiing in a rectangular field, the field can be represented as a grid of N rows and M columns, rows are numbered from 1 to N starting from top, columns are numbered from 1 to M starting from left, each cell has a a number representing the height of the snow on this particular part of the field.

after skiing for a while in the field they decided to play a game,  first hasan has to choose a set of cells S not necessarily adjacent and show this set to Chef.

after that, Chef has to choose exactly one cell d not necessarily from set S and tell it to Hasan.

finally, Hasan has to choose one cell from set S and start skiing from that cell and try to reach cell d that the chef just chose, if he couldn't then Chef wins, otherwise Hasan wins. 

When Hasan is skiing, he can move from one cell to another iff both cells are adjacent (they share a side) and the height of destination cell is not more than the height of current cell.  

it's obvious that it's easy for Hasan to win this game, because he can simply choose all cells to be in set S, but he want the set S to have minimum number of cells to prove that he is very skilled in skiing.

knowing that both players play optimally, please help Hasan to find minimum number of cells to be in set S to guarantee the winning for him.

------ Input ------ 

First line contains integer T donating the number of test-cases.
First line of each test-case contains two integers n and m donating the number of rows and columns respectively.
Each of the following n lines contains m numbers donating the heights of the field

------ Output ------ 

For each test-case output a single line containing a single integer donating minimum number of cells has to be in set S so that Hasan guarantee winning 

------ Constraints ------ 

Should contain all the constraints on the input data that you may have. Format it like:

$1 ≤ T ≤ 100$
$1 ≤ N, M ≤ 1,000$
$1 ≤ sum of N in all test-cases ≤ 1,000$
$1 ≤ sum of M in all test-cases ≤ 1,000$
$1 ≤ height of snow ≤ 1,000,000,000$

----- Sample Input 1 ------ 
2
3 3
1 2 2
2 1 1
2 1 1
3 3
3 2 2
2 1 1
2 1 1
----- Sample Output 1 ------ 
2
1
----- explanation 1 ------ 
Example case 1. Hasan has to select at least two cells to be in S so that he guarantee he can reach all other cells starting from anyone of them, example of cells to choose (2,1) and (1,2)

Example case 2. if Hasan chose cell (1,1) to be in S then he can reach any cell starting from it and thus guarantee winning

Source: codechef | Difficulty: HARD
Tags: Graph algorithms

Graph traversal

Directed graphs

Strong connectivity

Sorting

Greedy algorithms

Data structures


Solutions:
import sys
sys.setrecursionlimit(1000000)

def rec(a, arr, i, j, n, m):
	if arr[i][j] == 1:
		return
	arr[i][j] = 1
	if i - 1 >= 0:
		if a[i - 1][j] == a[i][j]:
			rec(a, arr, i - 1, j, n, m)
	if i + 1 < n:
		if a[i + 1][j] == a[i][j]:
			rec(a, arr, i + 1, j, n, m)
	if j - 1 >= 0:
		if a[i][j - 1] == a[i][j]:
			rec(a, arr, i, j - 1, n, m)
	if j + 1 < m:
		if a[i][j + 1] == a[i][j]:
			rec(a, arr, i, j + 1, n, m)
for x in range(int(input())):
	(n, m) = [int(i) for i in input().strip().split()]
	a = [[int(i) for i in input().strip().split()] for j in range(n)]
	arr = [[0] * m for i in range(n)]
	ans = 0
	for i in range(n):
		for j in range(m):
			if arr[i][j] == 0:
				if i - 1 >= 0:
					if a[i - 1][j] > a[i][j]:
						rec(a, arr, i, j, n, m)
						continue
				if i + 1 < n:
					if a[i + 1][j] > a[i][j]:
						rec(a, arr, i, j, n, m)
						continue
				if j - 1 >= 0:
					if a[i][j - 1] > a[i][j]:
						rec(a, arr, i, j, n, m)
						continue
				if j + 1 < m:
					if a[i][j + 1] > a[i][j]:
						rec(a, arr, i, j, n, m)
						continue
	for i in range(n):
		for j in range(m):
			if arr[i][j] == 0:
				rec(a, arr, i, j, n, m)
				ans += 1
	print(ans)


def solve(x, n, m):

	def nbrs(i, j):
		ret = []
		for a in [i - 1, i + 1]:
			if a >= 0 and a < n:
				ret += [(a, j)]
		for a in [j - 1, j + 1]:
			if a >= 0 and a < m:
				ret += [(i, a)]
		return ret

	def islmax(i, j):
		h = x[i][j]
		for (a, b) in nbrs(i, j):
			if x[a][b] > h:
				return False
		return True

	def fill(ii, jj):
		q = [(ii, jj)]
		bb[ii][jj] = 1
		while q:
			(i, j) = q[0]
			q = q[1:]
			h = x[i][j]
			for (a, b) in nbrs(i, j):
				if bb[a][b]:
					continue
				h0 = x[a][b]
				if h0 <= h:
					bb[a][b] = 1
					q += [(a, b)]
	bb = [[0 for i in range(m)] for j in range(n)]
	pts = [(x[i][j], i, j) for i in range(n) for j in range(m)]
	pts = sorted(pts)[::-1]
	ret = 0
	for (z, i, j) in pts:
		if bb[i][j]:
			continue
		if islmax(i, j):
			ret += 1
			fill(i, j)
	return ret
import sys
f = sys.stdin
t = int(f.readline())
for i in range(t):
	(n, m) = map(int, f.readline().split())
	x = []
	for j in range(n):
		x += [list(map(int, f.readline().split()))]
	print(solve(x, n, m))


T = int(input())
move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
for _ in range(T):
	(N, M) = [int(c) for c in input().strip().split()]
	S = []
	for i in range(N):
		row = [int(c) for c in input().strip().split()]
		S.append(row)
	visited = []
	for i in range(N):
		visited.append([0] * M)
	nbSol = 0
	while True:
		maxindex = []
		maxrow = []
		for i in range(N):
			m = max(S[i])
			maxrow.append(m)
			maxindex.append(S[i].index(m))
		m = max(maxrow)
		r = maxrow.index(m)
		c = maxindex[r]
		if m == -1:
			break
		tovisit = []
		tovisit.append([r, c])
		while len(tovisit) != 0:
			(x, y) = tovisit.pop(0)
			h = S[x][y]
			S[x][y] = -1
			for (ix, iy) in move:
				nx = x + ix
				ny = y + iy
				if nx >= 0 and nx < N and (ny >= 0) and (ny < M) and (visited[nx][ny] == 0) and (S[nx][ny] <= h):
					visited[nx][ny] = 1
					tovisit.append([nx, ny])
		nbSol = nbSol + 1
	print(nbSol)


from time import time
startTime = time()
T = int(input())
for _ in range(T):
	(H, W) = [int(x) for x in input().split()]
	A = [[int(x) for x in input().split()] for row in range(H)]
	peaksChosen = 0
	peaksToCheck = []
	tilesLeft = H * W
	while tilesLeft > 0:
		if len(peaksToCheck) == 0:
			(bestPeakHeight, bestPeakLocation) = (-1, (None, None))
			for R in range(H):
				if max(A[R]) > bestPeakHeight:
					(bestPeakHeight, bestPeakLocation) = (max(A[R]), (R, A[R].index(max(A[R]))))
			peaksToCheck.append((bestPeakLocation[0], bestPeakLocation[1], bestPeakHeight))
			peaksChosen += 1
			A[bestPeakLocation[0]][bestPeakLocation[1]] = 0
			tilesLeft -= 1
		while len(peaksToCheck) > 0:
			(R, C, V) = peaksToCheck.pop(0)
			if R != 0 and V >= A[R - 1][C] > 0:
				peaksToCheck.append((R - 1, C, A[R - 1][C]))
				A[R - 1][C] = 0
				tilesLeft -= 1
			if C != W - 1 and V >= A[R][C + 1] > 0:
				peaksToCheck.append((R, C + 1, A[R][C + 1]))
				A[R][C + 1] = 0
				tilesLeft -= 1
			if R != H - 1 and V >= A[R + 1][C] > 0:
				peaksToCheck.append((R + 1, C, A[R + 1][C]))
				A[R + 1][C] = 0
				tilesLeft -= 1
			if C != 0 and V >= A[R][C - 1] > 0:
				peaksToCheck.append((R, C - 1, A[R][C - 1]))
				A[R][C - 1] = 0
				tilesLeft -= 1
	print(peaksChosen)