小可爱先生的约会(luogu U244984)

题目传送门->https://www.luogu.com.cn/problem/U244984<-

本人原创题目

题目背景

众所周知，小可爱先生不仅拥有俊俏的容颜，还拥有惊人的才华：liaomei。

是的，你没有听错。就在今天晚上，小可爱先生又要去约会了，可是他貌似遇到了麻烦，请求同样帅气（美丽）的…你…的同学（你的闺蜜/基友）去救他，还要求你为他想出办法，好让你的好盆友和小可爱先生的惊吓度尽量低，身为s*，你不得不接受这次委托。

小可爱先生和你的好盆友将会从（1，1）走到（n，n）

但是…你有这么善良吗？很明显没有，因为你的好盆友平时就和小可爱先生一起欺负你，所以，你编写了一个程序，计算如何安排计划才可以使他们危险度最高，但不至于趋势。

接下来，就是你…的手，表演的时候了！

题目描述

现在，给予你小可爱先生约会的n*n平面地图，“.”表示可以通行，“#”表示不能通行，走过的格子会立马塌陷下去，有些格子会给出惊吓度s（有惊吓度的格子说明一定可以走），说明这个格子一旦走上去，就会出现惊吓度为s的小可爱，这时他们俩就会受到s的惊吓，当一次惊吓超过了其中一人所能承受的惊吓度，那个人就会趋势，另一个人也会因为同伴的趋势而趋势。

但你安排的路要是他们累计所受到的惊吓度最高，但s不了。

最后输出所需的步数还有累计最大的惊吓度，如果他们必s无疑，则输出“Oh,dead...Well,that's great.”

输入格式

第一行n

接下来n行，每行n个数，代表小可爱先生约会地点的n*n平面图。

然接下来一行是两个整数，s1，s2代表小可爱先生和你的好盆友所能承受的最大的惊吓度。

输出格式

你不能保证他们一定能活着。

如果他们回来了，请在第一行输出要走多少步才能到，第二行一个整数，代表他们所受到的惊吓值累积。

如果不能回来，请输出“Oh,dead...Well,that's great.”。

样例输入

5
..#..
.1.35
##.#.
.#2.#
..#22
2 2

样例输出

8
7

说明/提示

1<=n<10

1<=s,s1,s2<=9

温馨提示：

1.走过的地方不能再走了。

2.两个人必须一起走，不能分开。

3.答案路径要求是最高惊吓度中的最短路径。

c++代码1：

#include<bits/stdc++.h>
using namespace std;
const int N=15;
char m[N][N];
int s1,s2,n,max1=-1,max2=-1,xx[4]={1,0,-1,0},yy[4]={0,1,0,-1},d1,d2;
bool vis[N][N];
void search1(int x,int y,int s,int d)
{
	if (x==n-1 && y==n-1 && max1<s)
	{
		max1=max(max1,s);
		d1=d;
	}
	for (int i=0;i<4;i++)
	{
		int x1=x+xx[i],y1=y+yy[i];
		if (x1>=0 && x1<n && y1>=0 && y1<n && !vis[x1][y1] && m[x1][y1]!='#' && m[x1][y1]-'0'<=s1)
		{
			vis[x][y]=1;
			if(m[x1][y1]=='.') search1(x1,y1,s,d+1);
			else search1(x1,y1,s+(m[x1][y1]-'0'),d+1);
			vis[x][y]=0;               //回溯
		}
	}
}
void search2(int x,int y,int s,int d)
{
	if (x==n-1 && y==n-1 && max2<s)
	{
		max2=max(max2,s);
		d2=d;
	} 
	for (int i=0;i<4;i++)
	{
		int x1=x+xx[i],y1=y+yy[i];
		if (x1>=0 && x1<n && y1>=0 && y1<n && !vis[x1][y1] && m[x1][y1]!='#' && m[x1][y1]-'0'<=s2)
		{
			vis[x][y]=1;
			if(m[x1][y1]=='.') search2(x1,y1,s,d+1);
			else search2(x1,y1,s+(m[x1][y1]-'0'),d+1);
			vis[x][y]=0;               //回溯
		}
	}
}
int main()
{
	scanf("%d",&n);
	for (int i=0;i<n;i++) scanf("%s",m[i]);
	scanf("%d%d",&s1,&s2);
	search1(0,0,0,0);
	search2(0,0,0,0);
	if (max1==-1 || max2==-1) printf("Oh,dead...Well,that's great.");
	else printf("%d\n%d",max(d1,d2),max(max1,max2));
	return 0;
}

c++代码2：

#include<iostream>
#include<cstring>
using namespace std;
int a[15][15];
bool f[15][15];
int dx[5] = {0,0,1,0,-1};
int dy[5] = {0,1,0,-1,0};
char c;
int n,s1,s2,maxn = -2e9,k = 2e9,cnt;
void dfs(int x,int y,int sum)
{
	if (x == y & y == n){
		if (sum > maxn ){
			maxn = sum;
			k = cnt;
		}
		else if (sum == maxn){
			k = min(k,cnt);
		}
		return;
	}
	for (int i = 1;i <= 4;i++)
	{
		int x1 = x + dx[i],y1 = y + dy[i];
		if (f[x1][y1] | a[x1][y1] == -1) continue;
		f[x1][y1] = true;
		cnt++;
		dfs(x1,y1,sum+a[x1][y1]);
		f[x1][y1] = false;
		cnt--;
	}
	return;
}

int main()
{
	cin >> n;
	for (int i = 1;i <= n;i++)
	for (int j = 1;j <= n;j++){
		cin >> c;
		if (c == '.') a[i][j] = 0;
		else if (c == '#') a[i][j] = -1;
		else a[i][j] = (c - '0');
	}
	cin >> s1 >> s2;
	for (int i = 0;i <= n+1;i++)
	for (int j = 0;j <= n+1;j++){
		if (a[i][j] > s1 | a[i][j] > s2 | i == 0 | j == 0 | i == n + 1 || j == n + 1)
			a[i][j] = -1;
	}
	
	f[1][1] = true;
	dfs(1,1,0);
	if (maxn != -2e9)
		cout << k  << '\n' << maxn ;
	else 
		cout << "Oh,dead...Well,that's great.";
	return 0;	
}