问题标题: 酷町堂：1257 迷宫寻宝

Question

0

王子健

初级天翼

1257 迷宫寻宝经验值：800

题目描述 Description

小王设计了一个9行9列的迷宫：

1,1,1,1,1,1,1,1,1

1,0,0,1,0,0,1,0,1

1,0,0,1,1,0,0,0,1

1,0,1,0,1,1,0,1,1

1,0,0,0,0,1,0,0,1

1,1,0,1,0,1,0,0,1

1,1,0,1,0,0,0,0,1

1,1,1,1,1,1,1,1,1

0表示道路，1表示墙。

现在输入一个坐标作为起点，再如输入一个坐标作为宝贝的存放位置，问现在由你从起点出发，最少经过多少步可以寻的宝贝

输入描述 Input Description

第一行输入一个整数n（0<n<=100），表示有n组测试数据;
随后n行,每行有四个整数a,b,c,d（0<=a,b,c,d<=8）分别表示起点的行、列，宝贝的行、列。

输出描述 Output Description

输出最少走几步。

样例输入 Sample Input

2 3 1 5 7 3 1 6 7

样例输出 Sample Output

12 11

总是算不对，BFS的算法怎么写，大佬指教

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

struct NODE{
    int x, y;
};

queue<NODE> q;
int n, sx, sy, ex, ey, cnt;
int G[10][10] = {{1,1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,1,0,1}, {1,0,0,1,1,0,0,0,1}, {1,0,1,0,1,1,0,1,1}, {1,0,0,0,0,1,0,0,1}, {1,1,0,1,0,1,0,0,1}, {1,1,0,1,0,1,0,0,1}, {1,1,0,1,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1}}; 
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
bool flag, vis[10][10];
void bfs() {
    //起点入队 
    vis[sx][sy] = true;
    q.push(NODE{sx, sy});
    while(!q.empty()) {
        //1、取队首的点
        NODE t = q.front();
        if(t.x == ex && t.y == ey) { //队首是重点 
            flag = true;
            return ;
        }
        //2、把和队首直接相连的点加入队列
        for(int i=0; i<4; i++) {
            int nx = t.x + dir[i][0], ny = t.y + dir[i][1];
            if(nx>=1 && nx<=9 && ny>=1 && ny<=9 && G[nx][ny] == 0 && vis[nx][ny] == false) {
                vis[nx][ny] = true;
                q.push(NODE{nx, ny});

            }
        }
        //3、队首出队 
        q.pop();

    }
}

int main() {
    cin >> n ;
    while(n--) {
        cin >> sx >> sy >> ex >> ey;
        cnt = 0;
        flag = false;
        bfs();
        cout << cnt << endl; 
    }
    return 0;
}