3,4,5溢出
查看原帖
3,4,5溢出
1316800
b1049635337楼主2025/1/8 00:09

广度优先遍历,咋不行

#include <iostream>
#include <queue>

using namespace std;

bool isVisit[20][20];

//马的8个方位
int direction[8][2] = {
        {-1, -2},
        {1,  -2},
        {-2, -1},
        {2,  -1},
        {-2, 1},
        {2,  1},
        {-1, 2},
        {1,  2}
};

//卒可走的两个方位
int myDirec[2][2] = {
        {1,  0},
        {0,  1}
};

struct position {
    int x;
    int y;
};

//广度优先搜索,到达终点后,numOfPath++
int main() {
    int n, m, x, y;
    while (scanf("%d%d%d%d", &n, &m, &x, &y) != EOF) {
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < m + 1; j++) {
                isVisit[i][j] = false;
            }
        }
        isVisit[x][y] = true;
        for (int i = 0; i < 8; i++) {
            if (x + direction[i][0] >= 0 && x + direction[i][0] < n + 1 && y + direction[i][1] >= 0 &&
                y + direction[i][1] < m + 1) {
                isVisit[x + direction[i][0]][y + direction[i][1]] = true;
            }
        }

        int numOfPath = 0;//路径条数;
        queue<position> myQue;
        //起始点加入队列
        position start;
        start.x = 0;
        start.y = 0;
        myQue.push(start);

        //广度优先遍历
        while (!myQue.empty()) {
            position cur;
            cur = myQue.front();
            myQue.pop();

            if(cur.x == n && cur.y == m){
                numOfPath++;
                //break;
            }


            position neighbour;
            for (int i = 0; i < 2; i++) {
                if (cur.x + myDirec[i][0] >= 0 && cur.x + myDirec[i][0] < n + 1 && cur.y + myDirec[i][1] >= 0 &&
                    cur.y + myDirec[i][1] < m + 1 && !isVisit[cur.x + myDirec[i][0]][cur.y + myDirec[i][1]]){
                    neighbour.x = cur.x + myDirec[i][0];
                    neighbour.y = cur.y + myDirec[i][1];
                    myQue.push(neighbour);
                }
            }
        }

        printf("%d\n",numOfPath);

    }

    return 0;
}

2025/1/8 00:09
加载中...