欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

牛客寒假算法基础集训营4 Applese 走迷宫 /*贴个简单dfs迷宫*/

程序员文章站 2022-05-20 20:25:54
...

链接:https://ac.nowcoder.com/acm/contest/330/C
来源:牛客网

Applese 走迷宫
时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld

题目描述
精通程序设计的 Applese 双写了一个游戏。
在这个游戏中,它被困在了一个 n×m的迷宫中,它想要逃出这个迷宫。
在迷宫中,有一些方格是水池,只有当 Applese 处于水属性的时候才可以通过;有一些方格是岩浆,只有当 Applese 是火属性的时候可以通过;有一些方格是墙壁,无论如何都无法通过;另一些格子是空地(包括起点和终点),可以*通过。在一些空地上有神秘道具可以让 Applese 转换自己的属性(从水属性变为火属性或从火属性变为水属性,需要一个单位的时间)。
已知 Applese 在一个单位的时间内可以朝四个方向行走一格,且开始处于水属性,位于空地的道具拾取后只能在该处立即使用(或者不使用),且可以多次使用。求它走出迷宫需要的最少时间。

输入描述:
第一行两个正整数 n, m 表示迷宫的大小。
接下来 n 行,每行长度为 m 的字符串。描述地图。
其中 ‘S’ 表示起点,‘T’ 表示终点,’.’ 表示空地,‘w’表示岩浆,’~‘表示水池,’@’ 表示道具,’#'表示障碍。
保证地图中的起点和终点只有一个,道具都位于空地。

输出描述:
输出一个整数,表示 Applese 走出迷宫的最短时间。特别地,如果 Applese 走不出迷宫,输出 “-1”。

示例1
输入
5 5
[email protected]
.S#…
~w#…
.w…~
@w.~T

输出
18
备注:
1≤n,m≤100

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define mod 1000000007
#define MAXN 1000005
#define pai acos(-1)
int n,m,re=INT_MAX;
char mp[105][105];
int go[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
int sh,sl,eh,el;
int dp[105][105][2];/*0水 1火*/
void dfs(int h,int l,int sta,int s){
     /*if(h==1&&l==1){
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++)
                printf("%d ",dp[i][j][1]);
            cout <<endl;
        }
     }*/
     if(min(dp[eh][el][0],dp[eh][el][1])!=INT_MAX&&s+abs(h-eh)+abs(l-el)>=min(dp[eh][el][0],dp[eh][el][1])) return;/*剪枝*/
     if(s>=dp[h][l][sta]) return;/*剪枝*/
     dp[h][l][sta]=s;
     if(mp[h][l]=='T'){
        return;
     }
     for(int i=0;i<4;i++){
        int th=h+go[i][0];
        int tl=l+go[i][1];
        if(th<0||tl<0||th>n-1||tl>m-1) continue;
        if(mp[th][tl]=='~'&&sta==1) continue;
        if(mp[th][tl]=='w'&&sta==0) continue;
        if(mp[th][tl]=='#')continue;

        if(mp[th][tl]=='@'){
            dfs(th,tl,sta,s+1);
            dfs(th,tl,sta^1,s+2);
        }
        else{
            dfs(th,tl,sta,s+1);
        }
    }
}
int main()
{

    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
        cin>>mp[i];
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++){
            dp[i][j][0]=INT_MAX;
            dp[i][j][1]=INT_MAX;
        }
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++){
            if(mp[i][j]=='S'){
                sh=i;
                sl=j;
            }
            if(mp[i][j]=='T'){
                eh=i;
                el=j;
            }
        }
    dfs(sh,sl,0,0);
    int re=min(dp[eh][el][0],dp[eh][el][1]);
    if(re==INT_MAX){
        cout<<-1;
    }
    else cout << re;
    return 0;
}

相关标签: 迷宫