版权声明：转载请注明出处。 https://blog.csdn.net/u014427196/article/details/42266111

http://poj.org/problem?id=3984 

#include<stdio.h>  
#include<iostream>  
#include<math.h>  
#include<stdlib.h>  
#include<ctype.h>  
#include<algorithm>  
#include<vector>  
#include<string.h>  
#include<queue>  
#include<stack>  
#include<set>  
#include<map>  
#include<sstream>  
#include<time.h>  
#include<utility>  
#include<malloc.h>  
#include<stdexcept>  
#include<iomanip>  
#include<iterator>  

using namespace std;

int n, m;
int p[35][35];

int vis[6][6];
int dir[4][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

struct node
{
    int x;
    int y;
};

struct node pre[30][30];//存储节点前一个位置

int check(int x, int y)
{
    if (x >= 0 && x < 5 && y >= 0 && y < 5)
        return 1;
    return 0;
}

void printf_path()
{
    stack<node> path;//栈用来保存路径
    node ss;
    ss.x = 4;
    ss.y = 4;

    while (1)
    {
        path.push(ss);
        if (!ss.x && !ss.y)
            break;
        ss = pre[ss.x][ss.y];


    }
    while (!path.empty())
    {
        ss = path.top();
        path.pop();

        printf("(%d, %d)\n",ss.x,ss.y);
    }
}

void bfs()
{
    memset(vis,0,sizeof(vis));

    queue <node> q;
    node qq, qqq;

    qq.x = 0;
    qq.y = 0;
    vis[0][0] = 1;

    q.push(qq);

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

        if (qq.x == 4 && qq.y == 4)
        {    
            printf_path();
            return;
        }
        for (int i = 0; i < 4;i++)
        {
            int x = qq.x + dir[i][0];
            int y = qq.y + dir[i][1];

            if (!check(x,y) || vis[x][y] || p[x][y] == 1)
                continue;

            qqq = qq;
            qqq.x = x;
            qqq.y = y;

            pre[qqq.x][qqq.y] = qq;

            vis[x][y] = 1;
            q.push(qqq);
        }
    }
    return;
}


int main()
{
        for (int i = 0; i < 5; i++)
        {
            for (int j = 0; j < 5; j++)
            {
                cin >> p[i][j];
            }
        }

        bfs();

    return 0;
}