求助

P1746 离开中山路

szlh_XJS @ 2023-04-22 09:44:19

#include<iostream>
#include<string.h>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<time.h>
#include<stdlib.h>
#include<vector>
#include<stack>
#include<ctype.h>
#include<cstring>
using namespace std;
int n,a,b,c,d;
string nn[1005];
void dfs(int i,int j,int s)
{
    if(i<1||j<0||i>n||j>n-1||nn[i][j]=='1')
    {
        return ;
    }
    if(i==c&&j==d)
    {
        cout<<s;
        exit(0);
    }
    s++;
    dfs(i+1,j,s);
    dfs(i-1,j,s);
    dfs(i,j-1,s);
    dfs(i,j+1,s);
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>nn[i];
    }
    cin>>a>>b>>c>>d;
    dfs(a,b,0);
    cout<<-1;
    return 0;
}

第一次

#include<iostream>
#include<string.h>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<time.h>
#include<stdlib.h>
#include<vector>
#include<stack>
#include<ctype.h>
#include<cstring>
using namespace std;
int n,a,b,c,d;
string nn[1005];
void dfs(int x,int y,int s)
{
    if(nn[x][y]=='1'||x<1||y<0||x>n||y>n-1)
    {
        return ;
    }
    if(x==c&&y==d-1)
    {
        cout<<s;
        exit(0);
    }
    s++;
    nn[x][y]='1';
    dfs(x-1,y,s);
    dfs(x,y+1,s);
    dfs(x-1,y,s);
    dfs(x,y+1,s);
 } 
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>nn[i];
    }
    cin>>a>>b>>c>>d;
    dfs(a,b-1,0);
    cout<<-1;
    return 0;
}

第二次


by _maojun__ @ 2023-04-22 09:49:55

@szlh6XJS 你这样 dfs 有可能绕了一圈然后给这个点打上一个不优的标记。

比如

01
32

其实 3 的那个点大可以一步走过去但是你直接标记了不让修改


by _maojun__ @ 2023-04-22 09:50:08

建议 bfs


by zjw806903 @ 2023-04-22 10:07:20

同上,建议bfs,dfs容易出错

因为本人就是用的bfs


by szlh_XJS @ 2023-04-22 11:30:47

@zjw806903 感谢大佬


by szlh_XJS @ 2023-04-22 11:31:01

@zjw806903 感谢大佬


|