广搜求条

违规用户名K&xs3Z^ @ 2024-08-20 09:00:38

#include<bits/stdc++.h>
using namespace std;
queue<int> x;
queue<int> y;
char a[1110][1110];
int step=-1,n,s1,t1,s2,t2;
bool vis[1110][1110];
int fx[6]={0,0,1,0,-1};
int fy[6]={0,1,0,-1,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>>a[i][j];
    cin>>s1>>t1>>s2>>t2;
    x.push(s1),y.push(t1);
    while(!x.empty()){
        for(int i=1;i<=4;i++){
        int tx=x.front()+fx[i];
        int ty=y.front()+fy[i];
        if(a[tx][ty]=='0'&&!vis[tx][ty]){
            vis[tx][ty]=1;
            a[tx][ty]='1';
            step++;
            x.push(tx),y.push(ty);
            if(tx==s2&&ty==t2){
                cout<<step<<endl;
                return 0;
            }
        }
        }
        x.pop(),y.pop();
    }
    return 0;
}

by 违规用户名K&xs3Z^ @ 2024-08-20 09:12:57

@tireden 嗯嗯 我试试

by _WHITE_NIGHT_ @ 2024-08-20 09:13:07

@违规用户名K&xs3Z^

struct Pos { int x,y; };
queue <Pos> q;

by tireden @ 2024-08-20 09:14:33

@_WHITENIGHT 你这定义跟没定义一样

by 违规用户名K&xs3Z^ @ 2024-08-20 09:14:59

@_WHITENIGHT 谢谢 已关

by _WHITE_NIGHT_ @ 2024-08-20 09:15:27

@tireden 天才

by Deeplove_lzs @ 2024-08-20 09:16:21

@违规用户名K&xs3Z^

逆天

by tireden @ 2024-08-20 09:16:31

@_WHITENIGHT 最起码也得这样吧

struct Pos { 
    int x,y; 
    int step;
};
queue <Pos> q;

by 违规用户名K&xs3Z^ @ 2024-08-20 09:17:01

@chenyunxi1 包的

by LikablePie79015 @ 2024-08-20 09:18:26

@违规用户名K&xs3Z^

分两个队列也不是不行，因为我就喜欢这样写（）

#include <iostream>
#include <queue>
using namespace std;

int n;
int a[1010][1010];
int vis[1010][1010];
int sx, sy, ex, ey;

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
queue <int> qx, qy;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            char ch;
            cin >> ch;
            a[i][j] = ch - '0';
        }
    }
    cin >> sx >> sy >> ex >> ey;

    qx.push(sx);
    qy.push(sy);

    while (!qx.empty()) {
        int nx = qx.front();
        int ny = qy.front();
        if (nx == ex && ny == ey) {
            break;
        }
        for (int i = 0; i < 4; i++) {
            int cx = nx + dx[i];
            int cy = ny + dy[i];
            if (cx >= 1 && cx <= n && cy >= 1 && cy <= n && !a[cx][cy] && !vis[cx][cy]) {
                vis[cx][cy] = vis[nx][ny] + 1;
                qx.push(cx);
                qy.push(cy);
            }
        }
        qx.pop();
        qy.pop();
    }

    cout << vis[ex][ey];
    return 0;
}

by _WHITE_NIGHT_ @ 2024-08-20 09:22:09

@tireden 6

别人只是问如何用结构体定义数组而已，我这样写也是对的，只是写法不同。

#include<bits/stdc++.h>
using namespace std;

const int N = 1005;
struct Dot { int x,y; };
queue <Dot> mp;

int n,tarx,tary,begx,begy;
int vis[N][N],dis[N][N];
char chara;
int dx[] = {0,1,0,-1,0};
int dy[] = {0,0,-1,0,1};

int check(int x,int y)
{
    return x > 0 && x <= n && y > 0 && y <= n && vis[x][y] == 0;
}

int main()
{
    cin >> n;
    for(int i = 1;i <= n;i++)
    {
        scanf("\n");
        for(int j = 1;j <= n;j++)
        {
            scanf("%c",&chara);
            vis[i][j] = chara-'0';
        }
    }
    scanf("%d%d%d%d",&begx,&begy,&tarx,&tary);

    mp.push((Dot){begx,begy});
    vis[begx][begy] = 1;

    while(!mp.empty())
    {
        int nx = mp.front().x;
        int ny = mp.front().y;
        if(nx == tarx && ny == tary)
            return printf("%d",dis[nx][ny]) && 0;
        for(int i = 1;i <= 4;i++)
        {
            if(check(nx+dx[i],ny+dy[i]))
            {
                vis[nx+dx[i]][ny+dy[i]] = 1;
                mp.push((Dot){nx + dx[i],ny + dy[i]});
                dis[nx + dx[i]][ny + dy[i]] = dis[nx][ny]+1;
            }
        }
        mp.pop();
    }
}