10分求助

huanyue_ @ 2023-10-17 20:12:58

#include<iostream>
#include<cstring>
using namespace std;
int n,m,dx[4]={-1,1,0,0},dy[4]={0,0,-1,1},rec[107][107]={};
char mg[107][107];
bool flag=false;
void dfs(int x,int y)
{
    if(x==n&&y==m)
    {
        cout<<"Yes";
        exit(0);
    }
    else
    {
        for(int i=0;i<4;i++)
        {
            int xx=x+dx[i];
            int yy=y+dy[i];
            if(xx>=0&&xx<n&&yy>=0&&yy<m&&mg[xx][yy]=='.'&&rec[xx][yy]==0)
            {
                rec[xx][yy]=1;
                dfs(xx,yy);
                rec[xx][yy]=0;
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    memset(mg,'#',sizeof(mg));
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin>>mg[i][j];
        }
    }
    rec[0][0]=1;
    dfs(0,0);
    cout<<"No";
    return 0;
}

by chenxizhe2 @ 2023-10-17 20:25:25

很经典的动规这个和一个很像P2670 [NOIP2015 普及组] 扫雷游戏

by zgr20090920 @ 2023-10-20 19:13:11

1.不用记录是否走过，直接改为墙，不然超时（血泪史）； 2.最好从1开始存（应题目要求，不过从零开始应该也行）； 改完后代码如下（提交过，AC）：

#include<iostream>
#include<cstring>
using namespace std;
int n,m,dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
char mg[107][107];
bool flag=false;
void dfs(int x,int y)
{
    if(x==n&&y==m)
    {
        cout<<"Yes";
        exit(0);
    }
    else
    {
        for(int i=0;i<4;i++)
        {
            int xx=x+dx[i];
            int yy=y+dy[i];
            if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&mg[xx][yy]=='.')
            {
                mg[xx][yy]='#';
                dfs(xx,yy);
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    memset(mg,'#',sizeof(mg));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>mg[i][j];
        }
    }
    dfs(1,1);
    cout<<"No";
    return 0;
}

by huanyue_ @ 2023-10-23 18:33:26

@zgr20090920 谢大佬orz

by 202312904502clq @ 2023-12-23 21:02:44

为什么mg[xx][yy]不用在dfs()后面回溯一下，把mg[xx][yy]在赋为'.'??它难道不可能走回去分岔口后在另一条路吗？？？？