NOJ 1793シンプルダンジョン(裸BFSクラシック)

簡単な迷宮
時間制限(通常/Java):1000 MS/3000 MS実行メモリ制限:65536 KByte総提出:27テスト合格:12
説明
目を覚ますと、ボブは自分が迷宮に閉じ込められていることに気づいた.夢を見たのか.
いくら多くても、先に離れたほうがいい.しかし、恐怖のため、Bobは入り口から出口までの最短ルートを見つけたいと思っています.助けてもらえますか?
この迷路はかなり簡単で、N*Mの矩形領域で、各格子点は隣接する上下左右の4つの格子点に通じることができ、起点は(1,1)、終点は(N,M)である.このほか、迷路内にはK個の点が障害点であり、彼らが到達できないことを示しているが、障害点は起点と終点に現れない.
入力
グループデータ入力.
各グループのデータは、第1行N,M,K,2<=N,M<=50,0<=k<=N*M-2、
次にk行、各行の2つの整数xi,yiは、i番目の障害物の座標を表し、障害物の間に重複はなく、座標はいずれも1<=xi<=N、1<=yi<=Mである.
しゅつりょく
各グループのデータは1つの整数を出力して、最短の経路の長さ、もしBobが終点に着くことができないならば、出力-1;
サンプル入力
5 5 8 4 3 4 5 5 2 2 2 1 5 3 3 5 1 1 4 5 5 8 1 2 2 2 3 2 4 2 2 4 3 4 4 4 5 4
サンプル出力
8 16
 
タイトルリンク:http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1793
 
最简单的走迷宫,要求最短路,所以用BFS搜索
 

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
int const MAX = 55;
int map[MAX][MAX];
int vis[MAX][MAX];
int dirx[4] = {1,-1,0,0};   //    
int diry[4] = {0,0,-1,1};
int n, m, k;
struct Point
{
    int x, y;
    int step;
};

int BFS()
{
    memset(vis,0,sizeof(vis));  //   vis
    queue<Point> q;
    Point node, t;
    node.x = 1;
    node.y = 1;
    node.step = 0;
    vis[1][1] = 1;
    q.push(node);   //       
    while(!q.empty())   //         
    {
        node = q.front();   //      
        q.pop();            //    
        for(int i = 0; i < 4; i++)   //      
        {
            t = node;
            t.x += dirx[i];
            t.y += diry[i];
            t.step++;
            if(t.x == n && t.y == m)   //        
                return t.step;
            //        
            if(t.x < 1 || t.x > n || t.y < 1 || t.y > n || !map[t.x][t.y] || vis[t.x][t.y]) 
                continue;
            //         ，     
            else
            {
                vis[t.x][t.y] = 1;
                q.push(t);
            }
        }
    }
    return -1;
}

int main()
{
    int xi, yi;
    while(scanf("%d %d %d",&n, &m, &k) != EOF)
    {
        memset(map,1,sizeof(map));
        for(int i = 0; i < k; i++)
        {
            scanf("%d %d",&xi, &yi);
            map[xi][yi] = 0;
        }
        printf("%d
", BFS());
    }
}