NC20790. 刺客信条
描述
输入描述
第一行有两个整数，表示地图的行数n和列数m，地图为一个n×m的矩阵
接下来有n行，每行m个字符，每个字符是一个数字或大写字母，数字表示经过该建筑需要的时间，字母表示特定建筑（S表示佛罗伦萨的庄园，即起点；E表示梵蒂冈，即终点；A表示圣母百花大教堂；B表示圣马可大教堂；C表示乔托钟楼；A、B、C在每组数据中至多出现一次），每个字符或数字之间用空格分隔
为了降低游戏难度，小A特意调小了地图
0≤n,m≤30
输出描述
输出一个整数，从佛罗伦萨庄园到梵蒂冈的最小用时T
示例1
输入:
3 3 S A E 1 2 3 1 B 3
输出:
6
C++14(g++5.4) 解法, 执行用时: 918ms, 内存消耗: 504K, 提交时间: 2020-07-29 10:52:54
#include<bits/stdc++.h>
#define min(a,b) a<b?a:b
#define nx 50000
using namespace std;
char ch;
int mp[35][35];
int r,c,x[4]={-1,1,0,0},y[4]={0,0,-1,1};
int sr,sc,gr,gc,ans=0x3f3f3f3f;
bool vis[35][35];
void dfs(int a,int b,int now){
if(a==gr&&b==gc){
ans=min(ans,now);
return;
}
if(now>=ans)return;
for(int i=0;i<4;++i){
int nr=a+x[i],nc=b+y[i];
if(nr&&nr<=r&&nc&&nc<=c&&!vis[nr][nc]){
vis[nr][nc]=1;
dfs(nr,nc,now+mp[nr][nc]);
vis[nr][nc]=0;
}
}
}
int main(){
cin>>r>>c;
for(int i=1;i<=r;++i){
for(int j=1;j<=c;++j){
cin>>ch;
if(isdigit(ch))mp[i][j]=ch-'0';
if(ch=='A'||ch=='B'||ch=='C')mp[i][j]=100;
if(ch=='S')sr=i,sc=j;
if(ch=='E')gr=i,gc=j;
}
}
dfs(sr,sc,0);
cout<<ans;
}
C++(g++ 7.5.0) 解法, 执行用时: 955ms, 内存消耗: 500K, 提交时间: 2022-08-12 18:12:20
#include<bits/stdc++.h>
using namespace std;
char ch;
int mp[35][35];
int r,c,x[4]={-1,1,0,0},y[4]={0,0,-1,1};
int sr,sc,gr,gc,ans=0x3f3f3f3f;
bool vis[35][35];
void dfs(int a,int b,int now){
if(a==gr&&b==gc)
{
ans=min(ans,now);
return;
}
if(now>=ans)
{
return;
}
for(int i=0;i<4;++i)
{
int nr=a+x[i],nc=b+y[i];
if(nr&&nr<=r&&nc&&nc<=c&&!vis[nr][nc])
{
vis[nr][nc]=1;
dfs(nr,nc,now+mp[nr][nc]);
vis[nr][nc]=0;
}
}
}
int main(){
scanf("%d%d",&r,&c);
for(int i=1;i<=r;++i)
{
for(int j=1;j<=c;++j)
{
cin>>ch;
if(isdigit(ch))
{
mp[i][j]=ch-'0';
}
if(ch=='A'||ch=='B'||ch=='C')
{
mp[i][j]=100;
}
if(ch=='S')
{
sr=i;
sc=j;
}
if(ch=='E')
{
gr=i;
gc=j;
}
}
}
dfs(sr,sc,0);
printf("%d\n",ans);
}
C++ 解法, 执行用时: 638ms, 内存消耗: 504K, 提交时间: 2021-06-03 22:39:10
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int b[100][100],xx,yy,d[5]={0,1,0,-1,0},n,m;
int a[100][100],mn=0X3f3f3f;
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
void dfs(int x,int y,int s){
if(x==xx&&y==yy){
mn=min(mn,s);
return;
}
if(s>=mn) return;
for(int i=0;i<4;i++){
int l=x+dx[i],r=y+dy[i];
if(b[l][r]==0&&l>0&&r>0&&l<=n&&r<=m)
{
b[l][r]=1;
dfs(l,r,s+a[l][r]);
b[l][r]=0;
}
}
}
int main(){
int e,f;
char c;
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
cin>>c;
if(c=='S') e=i,f=j,b[i][j]=1;
else if(c=='A'||c=='B'||c=='C') a[i][j]=100;
else if(c=='E') xx=i,yy=j;
else a[i][j]=c-'0';
}
dfs(e,f,0);
cout<<mn;
return 0;
}