第二个点WA了
查看原帖
第二个点WA了
1460981
zdxc1987楼主2025/1/18 11:45
#include<bits/stdc++.h>
using namespace std;
int n, m;
int x_1, y_1, x_2, y_2;
char g[510][510];  // 地图
int vi[510][510];  // 状态
int move_x[5] = { 0,-1,0,1,0 };
int move_y[5] = { 0,0,1,0,-1 };
int flag = 1;

queue<pair<int, int>> q;
queue<pair<int, int>> q_0;  //  边权为0时候的队列
int bfs(int x, int y);
int bfs_0(int x, int y);

int bfs_0(int x, int y)
{ 
    q_0.push({ x,y });
    while (q_0.size() && flag)
    {
        pair<int, int> temp = q_0.front();
        q_0.pop();
        for (int i = 1; i <= 4; i++)
        {
            int a = temp.first + move_x[i]; int b = move_y[i] + temp.second;
            if (a < 0 || a > n - 1 || b < 0 || b > m - 1) continue;
            if (vi[a][b] != -1) continue;
            //  能不能走判断完毕,之后判断入队该在哪里入队

            if (g[a][b] != g[temp.first][temp.second])
            {
                vi[a][b] = vi[temp.first][temp.second] + 1;  //  这个ab点就不需要入队了
                q.push({ a,b });  //  入队的就是x+1的点,这样就满足了q的单调性
                
            }
            else
            {
                vi[a][b] = vi[temp.first][temp.second];
                q_0.push({ a,b });  // q_0入队
            }
            
            if (a == x_2 && b == y_2)
            {
                cout << vi[a][b] << endl;
                flag = 0;  //  相当于多个break的作用,让它直接停止
                return 0;
            }
            //q_0.push({a,b});     不需要再入队了,不一样的点不需要入队计算
        }
    }
    return 0;
}



int bfs(int x, int y) 
{
    memset(vi, -1, sizeof(vi));  //  -1 就代表没有走过这里
    vi[x][y] = 0;
    q.push({ x,y }); 
    while (q.size() && flag)
    {
        pair<int, int> temp = q.front();
        q.pop();
        for (int i = 1; i <= 4; i++)
        {
            int a = temp.first + move_x[i]; int b = move_y[i] + temp.second;
            if (a < 0 || a > n - 1 || b < 0 || b > m - 1) continue;
            if (vi[a][b] != -1) continue;
            if (g[a][b] == g[temp.first][temp.second])   //  若是相同先让这个点遍历到x+1的时候再回来
            {
                //q.pop();   //  之后就要continue了,所以在这里得提前将这个点移出去
                vi[a][b] = vi[temp.first][temp.second];  // 这个点要跟之前相同呀
                bfs_0(a, b);
                continue;
            }
            vi[a][b] = vi[temp.first][temp.second] + 1;
            if (a == x_2 && b == y_2)
            {
                cout << vi[a][b] << endl;
                flag = 0;
                return 0;
            }
            q.push({ a,b });

        }

    }
    return 0;
}

int main()
{
    while (1)
    {
        flag = 1;
        cin >> n >> m;
        if (n == m && n == 0)
            break;   
        //  清空队列
        while (q.size())
            q.pop();
        while (q_0.size())
            q_0.pop();
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                cin >> g[i][j];
        cin >> x_1 >> y_1 >> x_2 >> y_2;
        if (x_1 == x_2 && y_1 == y_2)
        {
            cout << 0 << endl;
            continue;

        }
        bfs(x_1, y_1);
    }
    return 0;
}

2025/1/18 11:45
加载中...