探险家（深搜）

题目描述

有一位探险家找到了一座大小为n×m的钻石宝藏，他现在已经通过了仪器探明了这座宝藏中的宝藏分布

为了使收益最大化，探险家需要按以下规则来收获宝藏：

• 每当探险家进入一个单元，就会收集该单元格中的所有宝藏。
• 探险家每次可以从当前位置向上下左右四个方向走。
• 每个单元格只能被进入一次。
• 不得进入宝藏数目为 0 的单元格。
• 矿工可以从网格中 任意一个 有宝藏的单元格出发或者是停止。

现在探险家想请你帮个忙，写一个程序帮他设计一条最优的路线，使探险家能够获取最大价值的宝藏。事成之后，他答应和你五五分成。

输入描述

测试样例由多组测试数据组成。每组测试数据第一行输入两个正整数 n 和 m ( 1≤n,m≤10 ）。接下来n行，每行输入m个整数mi​(0≤mi​≤100)分别代表当前单元格中的宝藏价值。

输出描述

输出探险家能够获得的最大宝藏价值。

测试样例1

输入

3 3
0 6 0
5 8 7
0 9 0

输出

24

测试样例2

输入

5 3
1 0 7
2 0 6
3 4 5
0 3 0
9 0 20

输出

28

提示

对于第一组测试样例：一种收集最多黄金的路线是：9−>8−>7。
对于第二组测试样例：一种收集最多黄金的路线是：1−>2−>3−>4−>5−>6−>7。

​
#include<bits/stdc++.h>
using namespace std;
int s[1010][1010];
int vis[1010][1010];
int sum=0;
int n,m;
int dir[4][2]={0,1,1,0,0,-1,-1,0};
void dfs(int x,int y,int ans){
	for(int i=0;i<4;i++){
		int tx=x+dir[i][0];
		int ty=y+dir[i][1];
		if(tx>=0 &&ty>=0 &&tx<n &&ty<m &&s[tx][ty]!=0 &&vis[tx][ty]==0){
			vis[tx][ty]=1;
			dfs(tx,ty,ans+s[tx][ty]);
			vis[tx][ty]=0;
		}		
	}
	sum=max(ans,sum);
return;
}
int main(){
	while(cin>>n>>m){
		sum=0;
		memset(vis,0,sizeof(vis));
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				cin>>s[i][j];
			}
		}
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				if(s[i][j]!=0){
					vis[i][j]=1;
					dfs(i,j,s[i][j]);	
					vis[i][j]=0;
				}
			}
		}
		cout<<sum<<endl;
	}
	return 0;
}
 
​