题目描述

时间：1s   空间：128M

 

题目描述：

最近探险家们在X国发现了一处遗迹，里面的地形复杂好比一个迷宫，但是里面有非常多的宝藏。

探险家们提前用“鹰眼”探查到了这个迷宫的地图结构，可以用一个二维图来表示。'#'代表无法跨越的陷阱，'*'代表可以去的位置，某些位置上存在宝藏，用一个数字表示这个宝藏的价值。遗迹特别神奇，某个位置一旦经过就会消失，不可再次到达。在迷宫中移动有上下左右四种方式。

探险家们想要知道从左上角的入口到达右下角的出口，最多可以获得多少宝藏？

 

输入格式：

第一行包含两个整数n，m，表示迷宫的大小。

接下来的n行，每行包含m个字符，代表迷宫（保证入口没有陷阱）。

 

输出格式：

一个整数。代表总共可获得的宝藏价值和，无法到达出口则输出-1

 

样例输入1：

5 6 
1****# 
*###2# 
4###*# 
*###1# 
**1***
 

样例输出1：

6
 

约定：

1 <= N，M<= 7，0<=宝藏价值<=9

我的代码

#include<bits/stdc++.h>
using namespace std;
int n,m,a[10][10];
int N,M;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
bool vis[20][20];
char ma[20][20];
int ans=-1;
void dfs(int x,int y,int val)
{
	if(x==N&&y==M)
	{
		ans=max(ans,val);
		return ;
	}
	for(int i=0;i<4;++i)
	{
		int nx=x+dx[i];
		int ny=y+dy[i];
		if(ma[nx][ny]!='#' and ma[nx][ny]!=0 and !vis[nx][ny])
		{
			vis[nx][ny]=1;
			dfs(nx,ny,val+(ma[nx][ny]=='*'?0:ma[nx][ny]-'0'));
			vis[nx][ny]=0;
		}
	}
}
int main()
{
	cin>>N>>M;
	for(int i=1;i=N;++i)
	{
		for(int j=1;j<=M;++j)
		{
			cin>>ma[i][j];
		}
	}
	vis[1][1]=1;
	dfs(1,1,(ma[1][1]=='*'?0:ma[1][1]-'0'));
	cout<<ans;
	return 0;
}

应该是一些小错误，请各位大佬看看