2014年西北工业大学机试第三题

 查找最长的长度，使用dfs。

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm> 
using namespace std;
int map[505][505];
int num = -1;
typedef struct node{
	int x,y;
	node(int x,int y):x(x),y(y){}
}Node;
vector<node>v1;
int n,m;
//加上之后转换成上下左右四个点 
void init(){
	v1.push_back(node(-1,0));
	v1.push_back(node(1,0));
	v1.push_back(node(0,-1));
	v1.push_back(node(0,1));
}
//判断下一个要行走的点是否符合标准 
bool judge(int x0,int y0,int x,int y){
	if(x < 0||x >= n){
		return false;
	}
	if(y < 0||y >= m){
		return false;
	}
	if(map[x][y] >= map[x0][y0]){
		return false;
	}
	return true;
}
void dfs(int x,int y,int step){
	if(num < step){
		num = step;//更新路径长度 
	}
	for(int i = 0;i < 4;i++){
		int a = x + v1[i].x;
		int b = y + v1[i].y;
		if(judge(x,y,a,b)){
			dfs(a,b,step+1);
		}
	}
}
int main(){
	
	init();
	cin>>n>>m;
	for(int i = 0;i < n;i++){
		for(int j = 0;j < m;j++){
			cin>>map[i][j];
		}
	}
	num = -1;
	for(int i = 0;i < n;i++){
		for(int j = 0;j < m;j++){
			dfs(i,j,1);//每一个点都需要走一遍 
			cout<<map[i][j]<<" "<<num<<endl;
		}
	}
	cout<<num<<endl;
	return 0;
}