Solution: Notice that the grid given can be made into a graph. 
          Compress each strongly connected component into a
          a vertex of that graph. Notice that a strongly connected
          component in this graph is just adjacent areas with the
          same height, and can be identified with flood fill. For
          each vertex of the new graph, find the number of indegree
          and outdegree edges. The vertices that are important are
          the ones with either zero indegree edges or zero outdegree
          edges. These vertices are the ones at the beginning or end
          of a path (you start there or you end up there). Make the 
          observation that the answer is the maximum of vertices with
          zero indegree edges and vertices with zero outdegree edges,
          since there is always some way to pair them up like that.

P.S: If you are using BFS as floodfill (like I did), do not put it
     in a separate function. Costed me multiple TLE's. TAT. Leaving
     the floodfill in the main function saves around 800 MS.

#include <iostream>
#include <cstdio>
#include <queue>
#include <list>
#include <cmath>
using namespace std;

const double Pi=acos(-1.0);
typedef long long LL;

#define Set(a, s) memset(a, s, sizeof (a))
#define Rd(r) freopen(r, "r", stdin)
#define Wt(w) freopen(w, "w", stdout)

typedef pair<int, int> point;
#define X first
#define Y second

#define MAX_R 501
#define MAX_C 501
int grid[MAX_R][MAX_C], vertex[MAX_R][MAX_C], R, C;
int indegree[MAX_R*MAX_C], outdegree[MAX_R*MAX_C];

int latestUse[MAX_R*MAX_C];

int main ()
{
	ios::sync_with_stdio(false);

	scanf("%d", &C);
	scanf("%d", &R);

	for (int i = 0; i < R; i++)
		for (int j = 0; j < C; j++)
			scanf("%d", &grid[i][j]);

	queue<point>bfs;
	int nvertex = 0, dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (!vertex[i][j]) {
				int c = ++nvertex;
				point start = point(j, i);

				vertex[start.Y][start.X] = c;
				bfs.push(point(j, i));

				while(bfs.size()) {
					point curr = bfs.front(); bfs.pop();
					int currColor = grid[curr.Y][curr.X];

					for (int i = 0; i < 4; i++) {
						point nxt = point(curr.X+dir[i][0], curr.Y+dir[i][1]);

						if (nxt.X>=0 && nxt.X<C && nxt.Y>=0 && nxt.Y<R) {
							if (!vertex[nxt.Y][nxt.X] && grid[nxt.Y][nxt.X]==currColor)
								bfs.push(nxt), vertex[nxt.Y][nxt.X] = c;
							else if (vertex[nxt.Y][nxt.X] && latestUse[vertex[nxt.Y][nxt.X]]!=c) {
								if (grid[nxt.Y][nxt.X]<currColor)
									outdegree[c]++, indegree[vertex[nxt.Y][nxt.X]]++;
								else if (grid[nxt.Y][nxt.X]>currColor)
									indegree[c]++, outdegree[vertex[nxt.Y][nxt.X]]++;
								latestUse[vertex[nxt.Y][nxt.X]] = c;
							}
						}
					}
				}
			}
		}
	}



	int zeroin = 0, zerout = 0;
	for (int i = 1; i <= nvertex; i++)
		zeroin += (indegree[i]==0),
		zerout += (outdegree[i]==0);

	if (nvertex==1) zeroin=zerout=0;
	printf("%d\n", max(zeroin, zerout));


	return 0;
}