POJ 的两题有关走迷宫题目

时间：2010-09-11 来源：sysuwhj

这两题典型是用dfs , bfs的迷宫题，两题都大同小异

这两题两种方法都可以做出来，随便熟练一下刚学的bfs , dfs算法

POJ 3752走迷宫

  1 #include<iostream>
  2 #include <queue>
  3  using namespace std;
  4 
  5  struct point
  6 {
  7     int x;
  8     int y;
  9     int step;
 10 };
 11  //上下左右
 12 point oper[4] = { {0, -1}, {0, 1}, {1, 0}, {-1, 0}};
 13 
 14 bool cango[100][100];
 15 bool isvisit[100][100];
 16 point P;
 17 point N;
 18 point goal;
 19 int row;
 20 int col;
 21 queue<point> Q;
 22 
 23 int minstep = 1000;
 24 void bfs();
 25 void dfs(point);
 26 int main()
 27 {
 28 
 29     char a;
 30     freopen("test.txt","r",stdin);
 31     cin >> row >> col;
 32     goal.x = row - 1;
 33     goal.y = col - 1;
 34     for (int i = 0; i < row; i++)
 35     {
 36         for (int j = 0; j < col; j++)
 37         {
 38             isvisit[i][j] = false;
 39             cin >> a;
 40             if (a == '.')
 41                 cango[i][j] = true;
 42             if (a == '#')
 43                 cango[i][j] = false;
 44         }
 45     }
 46     N.x = 0;
 47     N.y = 0;
 48     N.step = 1;
 49     //dfs(N);
 50     //cout << minstep << endl;
 51     bfs();
 52     return 0;
 53 
 54 }
 55 
 56 //深度搜索
 57 void dfs(point N)
 58 {
 59     if (N.x == goal.x && N.y == goal.y )
 60     {
 61         if (N.step < minstep)
 62             minstep = N.step;
 63     
 64         return ;
 65     }
 66     else
 67     {
 68         for (int i = 0; i < 4; i++)
 69         {
 70             P.x = N.x + oper[i].x;
 71             P.y = N.y + oper[i].y;
 72             P.step = N.step + 1;
 73 
 74             if (P.x>=0 && P.x < row  && P.y >= 0 && P.y <col && !isvisit[P.x][P.y] && cango[P.x][P.y])
 75             {
 76                 isvisit[P.x][P.y] = true;
 77                 dfs(P);
 78                 //isvisit[P.x][P.y] = false; 不需要还原状态
 79             }
 80         }
 81 
 82 
 83     }
 84 
 85 }
 86 
 87 //广搜
 88 void bfs()
 89 {
 90     N.x = 0;
 91     N.y = 0;
 92     N.step = 1;
 93 
 94     Q.push(N);
 95 
 96     while (!Q.empty())
 97     {
 98         N = Q.front();
 99         Q.pop();
100 
101         if (N.x == goal.x && N.y == goal.y)
102         {
103             cout << N.step << endl;
104             return;
105         }
106 
107         for (int i = 0; i < 4; i++)
108         {
109             P.x = N.x + oper[i].x;
110             P.y = N.y + oper[i].y;
111             P.step = N.step + 1;
112 
113             if (P.x>=0 && P.x < row  && P.y >= 0 && P.y < col && !isvisit[P.x][P.y] && cango[P.x][P.y])
114             {
115                 isvisit[P.x][P.y] = true;
116                 Q.push(P);
117             }
118         }
119     }
120 }

POJ 2790 迷宫







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

struct point
{
int x;
int y;
};

point oper[4] = { {0, -1}, {0, 1}, {1, 0}, {-1, 0}};


bool cango[100][100];
bool isvisit[100][100];
point P;
point S;
point goal;
queue<point> Q;
int n;
bool isfind = false;
void dfs(point);
void bfs();

int main()
{
    int num;
    char a;
    freopen("test.txt","r", stdin);

    cin >> num;

    for (int k = 0; k < num; k++)
    {
        cin >> n;
        for (int i = 0; i < n; i++)
        {
        for (int j = 0; j < n; j++)
        {
        isvisit[i][j] = false;
        cin >> a;
        if (a == '.')
        cango[i][j] = true;
        if (a == '#')
        cango[i][j] = false;
        }
        }
        cin >> S.x >> S.y;
        cin >> goal.x >> goal.y;
        if (!cango[S.x][S.y] || !cango[goal.x][goal.y])
            cout << "NO" << endl;
        else
        {
            //dfs(S);
            bfs();
            if (!isfind)
                cout << "NO" << endl;
            else
                cout << "YES" << endl;
        }
        isfind = false;
    }

    return 0;
}


void bfs()
{
    while(!Q.empty())
        Q.pop();

    Q.push(S);
    isvisit[S.x][S.y] = true;

    while (!Q.empty())
    {
        S = Q.front();
        Q.pop();

        if (S.x == goal.x && S.y == goal.y)
        {
            isfind = true;
            return;
        }
        else
        {
            for (int i = 0; i < 4; i++)
            {
                P.x = S.x + oper[i].x;
                P.y = S.y + oper[i].y;

                if (P.x>=0 && P.x <n  && P.y >= 0 && P.y <n && !isvisit[P.x][P.y] && cango[P.x][P.y])
                {
                    isvisit[P.x][P.y] = true;
                    Q.push(P);
                }
            }

        }
    }

}

void dfs(point N)
{
    if (N.x == goal.x && N.y == goal.y )
    {
        isfind = true;
        return ;
    }
    else
    {
    for (int i = 0; i < 4; i++)
    {
        P.x = N.x + oper[i].x;
        P.y = N.y + oper[i].y;


        if (P.x>=0 && P.x <n  && P.y >= 0 && P.y <n && !isvisit[P.x][P.y] && cango[P.x][P.y])
            {
                isvisit[P.x][P.y] = true;
                dfs(P);
                //isvisit[P.x][P.y] = false;
            }
        }


    }

}