#include<iostream>
#include<cstdio>
using namespace std;
struct Point
{
    int x, y;
};
Point start , end,path[N][N];
void showPath(int x, int y)
{
    if(x == start.x && y == start.y)
    {
        cout << "()"...
        return;
    }
    showPath(path[x][y]...);
    cout << "->(x, y)";
}
void bfs()
{
    queue<Point> mq;
    mq.push(start);
    while(mq.size())
    {
        Point p = mq.front();
        mq.pop();
        if(.....)
        {
            // 是否到达终点
        }
        for(int i = 0; i < 4; i ++)
        {
            int cx = , cy= ;
            if(...) //在范围内
            //
            path[cx][cy] = p;
            mq.push({cx, cy});
        }
    }
}
int main(void)
{

// 输入
bfs();
showPath(end.x, end.y);
    return 0;
}
#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 155;
int n, m, f;
int a[N][N];
bool vis[N][N];
int sx, sy, ex, ey;
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
struct Point
{
    int x, y;
};
Point myPath[N][N];

void initInput(void)
{
    ios::sync_with_stdio(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            cin >> a[i][j];
        }
    }
    cin >> sx >> sy >> ex >> ey;
}
void showPath(Point t)
{
    f = 1;
    if(t.x == sx && t.y == sy)
    {
        cout << "(" << t.x << "," << t.y << ")";
        return;
    }
    showPath(myPath[t.x][t.y]);
    cout << "->(" << t.x << "," << t.y << ")";
}
void handle(void)
{
    queue<Point> mq;
    myPath[sx][sy] = {sx, sy};
    mq.push({sx, sy});
    while(mq.size())
    {
        Point t = mq.front();
        mq.pop();
        if(t.x == ex && t.y == ey)
        {
            showPath({ex, ey});
            cout << endl;
            return;
        }
        for(int i = 0; i < 4; i++)
        {
            int cx = t.x + dx[i], cy = t.y + dy[i];
            if(cx < 1 || cy < 1 || cx > n || cy > m) continue;
            if(a[cx][cy] == 1) continue;
            if(vis[cx][cy]) continue;
            vis[cx][cy] = 1;
            myPath[cx][cy] = t;
            mq.push({cx, cy});
        }
    }

    if(f==0)
        cout << "no way" << endl;
}

int main(void)
{
    initInput();
    handle();
    return 0;
}

0 条评论

目前还没有评论...