1268: 迷宫问题

http://tjuacm.chaosheng.top/problem.php?id=1268
原来我的写法，能过样例，但WA

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 110;

int matrix[N][N];
bool vis[N][N];
int row[4] = {1, 0, -1, 0};
int col[4] = {0, -1, 0, 1}; 

struct node{
    int i, j;
    vector<vector<int> > path;
};

vector<vector<int> > bfs(){
    queue<node> q;
    node f;
    f.i = 0;
    f.j = 0;
    f.path.push_back({0, 0});
    q.push(f);
    vis[f.i][f.j] = true;

    while(!q.empty()){
        f = q.front();
        q.pop();

        //满足条件
        if(f.i == 4 && f.j == 4){
            return f.path;
        }

        node v; //新的状态 

        for(int i = 0; i < 4; i++){
            v.i = f.i + row[i];
            v.j = f.j + col[i];
            if(!vis[v.i][v.j] && matrix[v.i][v.j] != 1){
                vis[v.i][v.j] = true;
                vector<vector<int> > tmp = f.path;
                tmp.push_back({v.i, v.j});
                v.path = tmp;
                q.push(v);
            }
        }
    }
    //return NULL;
}

int main(){
    for(int i = 0; i < 5; i++){
        for(int j = 0; j < 5; j++){
            cin >> matrix[i][j];
        }
    }
    memset(vis, false, sizeof(vis));

    vector<vector<int> > ans = bfs();
    for(int i = 0; i < ans.size(); i++){
        printf("(%d, %d)\n", ans[i][0], ans[i][1]); 
    }

    return 0;
}

参考 https://www.cnblogs.com/veasky/p/10989259.html
思路没有错，改了存path的方法，AC

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> P;

int matrix[5][5];
bool vis[5][5];
int row[4] = {1, 0, -1, 0};
int col[4] = {0, 1, 0, -1}; 

struct node{
    int x, y;
    //vector<vector<int> > path;
    int flag; //指示path最后一个位置 
    P path[100];
};

void bfs(){
    queue<node> q;
    node f;
    f.x = 0;
    f.y = 0;
    f.flag = 0; 
    f.path[f.flag] = P(0, 0);
    q.push(f);
    vis[f.x][f.y] = true;

    while(q.size()){
        f = q.front();
        q.pop();

        //满足条件
        if(f.x == 4 && f.y == 4){
            for(int i = 0; i <= f.flag; i++){
                printf("(%d, %d)\n",f.path[i].first, f.path[i].second); 
            }
            return ; 
        }

        for(int i = 0; i < 4; i++){
            node v = f;
            v.x = f.x + row[i];
            v.y = f.y + col[i];
            v.flag++;
            if(v.x >= 0 && v.x < 5 && v.y >= 0 && v.y < 5 && !vis[v.x][v.y] && matrix[v.x][v.y] == 0){
                vis[v.x][v.y] = true;
                v.path[v.flag] = P(v.x, v.y);
                q.push(v);
            }
        }
    }
}

int main(){
    for(int i = 0;  i < 5; i++){
        for(int j = 0; j < 5; j++){
            cin >> matrix[i][j];
        }
    }
    memset(vis, false, sizeof(vis));

    bfs();


    return 0;
}

不死心又改了原来的，但是RuntimeError
应该是打印path出了问题。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

int matrix[5][5];
bool vis[5][5];
int row[4] = {1, 0, -1, 0};
int col[4] = {0, 1, 0, -1}; 

struct node{
    int x, y;
    vector<vector<int> > path;
};

void bfs(){
    queue<node> q;
    node f;
    f.x = 0;
    f.y = 0;
    f.path.push_back({0, 0});
    q.push(f);
    vis[f.x][f.y] = true;

    while(q.size()){
        f = q.front();
        q.pop();

        //满足条件
        if(f.x == 4 && f.y == 4){
            for(int i = 0; i < f.path.size(); ++i){
                printf("(%d, %d)\n", f.path[i][0], f.path[i][1]); 

            }
            return ;
        }

        for(int i = 0; i < 4; i++){
            node v = f;
            v.x = f.x + row[i];
            v.y = f.y + col[i];
            if(v.x >= 0 && v.x < 5 && v.y >= 0 && v.y < 5 && !vis[v.x][v.y] && matrix[v.x][v.y] == 0){
                vis[v.x][v.y] = true;
                v.path.push_back({v.x, v.y});
                q.push(v);
            }
        }
    }
}

int main(){
    for(int i = 0;  i < 5; i++){
        for(int j = 0; j < 5; j++){
            cin >> matrix[i][j];
        }
    }
    memset(vis, false, sizeof(vis));

    bfs();


    return 0;
}