U502673 Desert Temple 题解

· · 题解

传送门

根据题意，二维数组存图，从 (1,1) 开始按照 (x,y+1),(x+1,y),(x,y-1),(x-1,y) 的顺序 dfs ，用 ans 数组存路径，可以开 ansx 和 ansy 两个数组，也可以用 pair 或结构体。注意每走过一格用 vis 数组标记一下，每次都要回溯。找到第一个答案后输出结束整个程序。

\color{52C41A}AC$ $Code 
#include<bits\stdc++.h>                                                                                                                                   
#include<Windows.h>                                                                                                                                   
#define LL long long                                                                                                                                    
#define void int                                                                                                                                                                  
#define Fcin ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);                                                                                                                                    
using namespace std;                                                                                                                                    
const int N=1e5+100;                                                                                                                                    
struct node{                                                                                                                                    
    int x,y;                                                                                                                                    
}ans[N];                                                                                                                                    
int n,m,mx,my;                                                                                                                                    
int dx[]={0,1,0,-1};                                                                                                                                    
int dy[]={1,0,-1,0};//方向别搞错                                                                                                                                    
char s[25][25];                                                                                                                                    
bool vis[25][25];                                                                                                                                    
void dfs(int x,int y,int step,int life)                                                                                                                                    
{                                                                                                                                    
    if(life<=0) return;                                                                                                                                    
    if(x==mx && y==my)                                                                                                                                    
    {                                                                                                                                    
        for(int i=1;i<step;i++)                                                                                                                                    
            cout<<ans[i].x<<" "<<ans[i].y<<"\n";                                                                                                                                    
        cout<<life;                                                                                                                                    
        exit(0);//结束整个程序                                                                                                                                    
    }                                                                                                                                    
    for(int i=0;i<4;i++)                                                                                                                                    
    {                                                                                                                                    
        int xx=x+dx[i],yy=y+dy[i];                                                                                                                                    
        if(xx<1 || xx>n || yy<1 || yy>m || vis[xx][yy]) continue;                                                                                                                                    
        vis[xx][yy]=1;                                                                                                                                    
        ans[step].x=xx;                                                                                                                                    
        ans[step].y=yy;                                                                                                                                    
        if(s[xx][yy]=='*') dfs(xx,yy,step+1,life-10);//判断是否扣血                                                                                                                                    
        else dfs(xx,yy,step+1,life);                                                                                                                                    
        vis[xx][yy]=0;//回溯                                                                                                                                    
    }                                                                                                                                    
}                                                                                                                                    
int main()                                                                                                                                    
{                                                                                                                                    
    Fcin;                                                                                                                                    
    int y1,y1,y1,y1,y1,y1,y1,y1;//明目张胆                                                                                                                                                            
    cin>>n>>m;                                                                                                                                    
    for(int i=1;i<=n;i++)                                                                                                                                    让你抄了吗！
        for(int j=1;j<=m;j++)                                                                                                                                    
        {                                                                                                                                    
            cin>>s[i][j];                                                                                                                                    
            if(s[i][j]=='x') mx=i,my=j;//结束位置                                                                                                                                    
        }                                                                                                                                    
    ans[1].x=ans[1].y=vis[1][1]=1;//初始值                                                                                                                                    
    dfs(1,1,2,100);                                                                                                            让你c！                        
    cout<<"-1";                                                                                                                                    
    return 0;                                                                                                  aminuosi________________________                                  
}