WA20分求调，一直输出-1

常规
1

题目描述

最近探险家们在X国发现了一处遗迹，里面的地形复杂好比一个迷宫，但是里面有非常多的宝藏。探险家们提前用“鹰眼”探查到了这个迷宫的地图结构，可以用一个二维图来表示。'#‘代表无法跨越的陷阱，’*'代表可以去的位置，某些位置上存在宝藏，用一个数字表示这个宝藏的价值。遗迹特别神奇，某个位置一旦经过就会消失，不可再次到达。在迷宫中移动有上下左右四种方式。探险家们想要知道从左上角的入口到达右下角的出口，最多可以获得多少宝藏？

输入格式

第一行包含两个整数n，m，表示迷宫的大小。接下来的n行，每行包含m个字符，代表迷宫（保证入口没有陷阱）。

输出格式

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

样例

Input 1

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

Output 1

6

样例解释

这个测试样例中，一种可行的路径是：从(1,1)位置开始，向下，向下，向下，向下，向下，右移，右移，右移，右移，右移，到达(5,6)位置。在这个路径中，可以获得的宝藏价值是1+4+1=6。

数据范围

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

#include<bits/stdc++.h>
using namespace std;
int n,m,ans=-1,sum=0,dx[]={-1,0,0,1},dy[]={0,-1,1,0};
char a[11][11];
bool vis[11][11];
void dfs(int x,int y){
  if(x==n-1&&y==m-1)ans=max(ans,sum);
  for(int i=0;i<4;i++){
    x+=dx[i];
    y+=dy[i];
    if(x<0||y<0||x>=n||y>=n){
      x-=dx[i],y-=dx[i];
      continue;
    }if(!vis[x][y]&&a[x][y]!='#'){
      if(a[x][y]!='.')sum+=a[x][y]-'0';
      vis[x][y]=1;
      dfs(x,y);
      x-=dx[i],y-=dy[i];
      vis[x][y]=0;
      if(a[x][y]!='.')sum-=a[x][y]-'0';
    }
  }
}int main(){
  cin>>n>>m;
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      cin>>a[i][j];
    }
  }dfs(0,0);
  cout<<ans;
  return 0;
}
1 个赞