学步园

#include <iostream>
#include <stack>
using namespace std;

struct node
{
	int x, y;
};

const int maxn = 255;
int graph[maxn][maxn];
bool visited[maxn][maxn];

stack<node> st;

void search(int xl, int yl, int xh, int yh, int val)
{
	while(xl < xh && yl < yh)
	{
		if(graph[xl][yh] == val && !visited[xl][yh])
		{
			node n; n.x = xl; n.y = yh;
			st.push(n);
			visited[xl][yh] = true;
		}
		else if(graph[xl][yh] > val)
			yh--;
		else
			xl++;
		if(graph[xh][yl] == val && !visited[xh][yl])
		{
			node n; n.x = xh; n.y = yl;
			st.push(n);
			visited[xh][yl] = true;
		}
		if (graph[xh][yl] > val)
			xh--;
		else
			yl++;
	}
}

int main(void)
{
	freopen("1.txt", "r", stdin);
	
	int m, n, i, j;
	memset(graph, 0, sizeof(graph));
	memset(visited, false, sizeof(graph));
	
	cin >> m >> n;
	for(i = 0; i < m; ++i)
		for(j = 0; j < n; ++j)
			cin >> graph[i][j];
	
	search(0, 0, m-1, n-1, 5);
	
	while(!st.empty())
	{
		node n = st.top(); st.pop();
		cout << n.x << " " << n.y << endl;
	}

	return 0;
}

复杂度为O(max(M,N))

附测试数据

5 5
1 2 3 4 5
3 7 8 9 11
5 9 10 17 18
7 12 15 19 23
9 13 16 20 25