本萌新又卡题了！！！

问题讨论区 基础段
1

3. 宝藏迷宫Ⅰ

题目ID：9862必做题100分

最新提交：

Wrong Answer

20 分

历史最高：

Wrong Answer

20 分

时间限制: 1000ms

空间限制: 262144kB

题目描述

最近探险家们在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;
char a[105][105];
bool vis[105][105] = {};
int dx[4]{ 0,1,0,-1 };
int dy[4]{ -1,0,1,0 };
int sum = 0,num=0,minn=1e9;
void dfs(int x, int y) {
    if (a[x][y] == '1' || a[x][y] == '2' || a[x][y] == '3' || a[x][y] == '4' || a[x][y] == '5' || a[x][y] == '6' || a[x][y] == '7' || a[x][y] == '8' || a[x][y] == '9') {
        num += a[x][y] - '0';
    }
    if (x == n && y == m) {//到达目标点
        minn = min(num, minn);
        return;
    }
    else {
        for (int i = 0; i < 4; i++) {
            int xx = x + dx[i];
            int yy = y + dy[i];//记录新位置
            if (vis[xx][yy] == 0 && xx >= 1 && yy >= 1 && xx <= n && yy <= m && a[xx][yy] == '*') {
                vis[xx][yy] = 1;
                dfs(xx, yy);
                vis[xx][yy] = 0;
            }
        }
    }
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    vis[1][1] = 1;
    dfs(1, 1);
    if (minn != 1e9) {
        cout << minn;
    }
    else {
        cout << -1;
    }
    return 0;
}
2

@鲁子欣 边走边把这个格子的宝藏拿走（可以用bfs，简单一点）

3

不会 bfs

4

@鲁子欣 等我一下

1 个赞
5

OK

1 个赞
6

@鲁子欣 核心代码：

void f(int x,int y,int step,int cnt){
	if(x==n&&y==m){
		sum=max(sum,cnt);
		return ;
	}
	vis[x][y]=1;
	for(int i=0;i<4;i++){
		int tx=x+dx[i];
		int ty=y+dy[i];
		if(tx>=1&&ty>=1&&tx<=n&&ty<=m&&a[tx][ty]!='#'&&vis[tx][ty]==0){
			cnt+=a[x][y]-'0';
			f(tx,ty,step+1);
		}
	}
	vis[x][y]=0;
}
1 个赞
7

40

#include <bits/stdc++.h>
using namespace std;
int n, m;
char a[15][15];
bool vis[15][15] = {};
int dx[4]{ 0,1,0,-1 };
int dy[4]{ -1,0,1,0 };
int sum = 0, num = 0, mixn = -1;
void dfs(int x, int y) {
    if (x == n && y == m) {//到达目标点
        mixn = max(num, mixn);
        return;
    }
    else {
        for (int i = 0; i < 4; i++) {
            int xx = x + dx[i];
            int yy = y + dy[i];//记录新位置
            if (vis[xx][yy] == 0 && xx >= 1 && yy >= 1 && xx <= n && yy <= m && a[xx][yy] != '#') {
                vis[xx][yy] = 1;
                if (a[x][y] != '*') {
                    num += a[x][y] - '0';
                }
                dfs(xx, yy);
                vis[xx][yy] = 0;
                num -= (a[x][y] - '0');
            }
        }
    }
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    vis[1][1] = 1;
    dfs(1, 1);
    cout << mixn;
    return 0;
}
1 个赞
8

为什么有4个值

1 个赞
9

@周子寓

1 个赞
10

怎么了？x,y坐标，step是步数，不用管，cnt是价值

1 个赞
11

f(tx,ty,step+1);
为什么只有3个

1 个赞
12

@鲁子欣 忘改了，sorry

1 个赞
13 
void f(int x,int y,int step,int cnt){
	if(x==n&&y==m){
		sum=max(sum,cnt);
		return ;
	}
	vis[x][y]=1;
	for(int i=0;i<4;i++){
		int tx=x+dx[i];
		int ty=y+dy[i];
		if(tx>=1&&ty>=1&&tx<=n&&ty<=m&&a[tx][ty]!='#'&&vis[tx][ty]==0){
			cnt+=a[x][y]-'0';
			f(tx,ty,step+1,cnt);
		}
	}
	vis[x][y]=0;
}
1 个赞
14

怎么改

1 个赞
15

下面那个

1 个赞
16 
#include<bits/stdc++.h>
using namespace std;
char a[25][25];
int n, sum = -1, x, y, m, s = 0, vis[25][25];
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
void f(int x, int y, int step, int cnt) {
	if (x == n && y == m) {
		sum = max(sum, cnt);
		return;
	}
	vis[x][y] = 1;
	for (int i = 0; i < 4; i++) {
		int tx = x + dx[i];
		int ty = y + dy[i];
		if (tx >= 1 && ty >= 1 && tx <= n && ty <= m && a[tx][ty] != '#' && vis[tx][ty] == 0) {
			cnt += a[x][y] - '0';
			f(tx, ty, step + 1,cnt);
		}
	}
	vis[x][y] = 0;
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
		}
	}
	f(1, 1, 0, 0);
	cout << sum;
}
1 个赞
18

@周子寓

1 个赞
19

abaabab

1 个赞
20

模版来了

1 个赞
21

???

1 个赞