全RE，问题在哪？

Charlie_____ @ 2024-08-21 16:10:05

int dx[4]={1,-1,0,0};
int dy[4]={0,0,-1,1};
int bfs(int x,int y){
    if(x==endx&&y==endy)    return ans;
    g[x][y]=1;
    for(int i=0;i<4;i++){
        int xx=x+dx[i];
        int yy=y+dy[i];
if(xx<=n&&xx>=1&&yy<=n&&yy>=1&&mapmap[xx][yy]=='0'&&g[xx][yy]!=1){
            g[xx][yy]=1;
            bfs(xx,yy);
            ans++;
        }
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>mapmap[i][j];
        }
    }
    cin>>startx>>starty>>endx>>endy;
    cout<<bfs(startx,starty);
    return 0;
}

by 114514514htz @ 2024-08-21 16:14:05

@djfyxjs 能放全代码吗

by Charlie_____ @ 2024-08-21 16:15:25

#include<bits/stdc++.h>
using namespace std;
int n,g[1001][1001],ans;
char mapmap[1001][1001];
int startx,starty;
int endx,endy;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,-1,1};
int bfs(int x,int y){
    if(x==endx&&y==endy)    return ans;
    g[x][y]=1;
    for(int i=0;i<4;i++){
        int xx=x+dx[i];
        int yy=y+dy[i];
        if(xx<=n&&xx>=1&&yy<=n&&yy>=1&&mapmap[xx][yy]=='0'&&g[xx][yy]!=1){
            g[xx][yy]=1;
            bfs(xx,yy);
            ans++;
        }
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>mapmap[i][j];
        }
    }
    cin>>startx>>starty>>endx>>endy;
    cout<<bfs(startx,starty);
    return 0;
}

@114514514htz

by 114514514htz @ 2024-08-21 16:56:06

@djfyxjs 深搜过不了，改好的深搜和我的代码都放在下面了

深搜

#include<iostream>
using namespace std;
int n,g[1010][1010],ans = 1e9;
char mapmap[1010][1010];
int startx,starty;
int endx,endy;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,-1,1};
void dfs(int x,int y,int num){
    if(x==endx&&y==endy)
    {
        ans = min(ans,num);
        return;
    }
    if(num>ans) return;
    for(int i=0;i<4;i++){
        int xx=x+dx[i];
        int yy=y+dy[i];
        if(xx<=n&&xx>=1&&yy<=n&&yy>=1&&mapmap[xx][yy] == '0'&&g[xx][yy] == 0){
            g[xx][yy]=1;
            dfs(xx,yy,num+1);
            g[xx][yy]=0;
        }
    }
    return;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>mapmap[i][j];
        }
    }
    cin>>startx>>starty>>endx>>endy;
    g[startx][starty] = 1;
    dfs(startx,starty,0);
    cout<<ans;
    return 0;
}

AC广搜

#include<iostream>
#include<queue>
using namespace std;
const int N = 1e3+30;
int n,g[N][N];
char mapmap[N][N];
int startx,starty;
int endx,endy;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,-1,1};
struct node{
    int x,y,ans;
};
queue<node> q;
int bfs(){
    node a = {startx,starty,0};
    g[startx][starty] = 1;
    q.push(a);
    while(!q.empty())
    {
        node p = q.front();
        q.pop();
        if(p.x == endx && p.y == endy) return p.ans;
        for(int i=0;i<4;i++){
            int xx=p.x+dx[i];
            int yy=p.y+dy[i];
            if(xx<=n&&xx>=1&&yy<=n&&yy>=1&&mapmap[xx][yy] == '0'&&g[xx][yy] == 0){
                g[xx][yy]=1;
                q.push(node{xx,yy,p.ans+1});
            }
        }
    }
    return 0;
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>mapmap[i][j];
        }
    }
    cin>>startx>>starty>>endx>>endy;
    cout<<bfs();
    return 0;
}

by Charlie_____ @ 2024-08-21 17:18:58

@114514514htz 阿里嘎多~（bushi）

by 114514514htz @ 2024-08-21 17:33:30

@djfyxjs 看一下题目标签