http://oj.acm.zstu.edu.cn/JudgeOnline/problem.php?id=4434

题解：经典的走迷宫问题

C++版本一

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG

using namespace std;
typedef long long ll;
const int N=500+10;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m;
char a[N][N];
bool vis[N][N];
int b[4][2]={1,0,0,1,-1,0,0,-1};
struct node{
    int x,y;
    int cnt;

}s,f,tmp;
int bfs(){
    queue<node>q;
    s.x=1;
    s.y=1;
    s.cnt=0;
    q.push(s);
    memset(vis,0,sizeof(vis));
    vis[1][1]=1;
    while(!q.empty()){
        f=q.front();
        q.pop();
        if(f.x==n&&f.y==m){
            return f.cnt;
        }
        for(int i=0;i<4;i++){
            tmp.x=f.x+b[i][0];
            tmp.y=f.y+b[i][1];
            if(0<tmp.x&&tmp.x<=n&&0<tmp.y&&tmp.y<=m&&!vis[tmp.x][tmp.y]&&a[tmp.x][tmp.y-1]!='*'){
                tmp.cnt=f.cnt+1;
                vis[tmp.x][tmp.y]=1;
                q.push(tmp);
            }
        }

    }
    return -1;

}
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            scanf("%s",a[i]);
        cout << bfs() << endl;
    }

    //cout << "Hello world!" << endl;
    return 0;
}

C++版本二


#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int, int> P;
const int N = 5e2 + 10;

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
char mp[N][N];
int vis[N][N];
queue<P>que;
void solve(){
    int n, m, nx, ny;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) vis[i][j] = -1;
    for(int i = 1; i <= n; ++i) scanf("%s", mp[i] + 1);
    P now = {1, 1};
    vis[1][1] = 0;
    while(!que.empty()) que.pop();
    que.push(now);
    while(!que.empty()){
        now = que.front(); que.pop();
        for(int i = 0; i < 4; ++i){
            nx = now.fi + dx[i];
            ny = now.se + dy[i];
            if(vis[nx][ny] != -1 || !nx || nx == n + 1 || !ny || ny == m + 1 || mp[nx][ny] == '*')   continue;
            vis[nx][ny] = vis[now.fi][now.se] + 1;
            if(nx == n && ny == m){
                printf("%d\n", vis[nx][ny]);
                return;
            }
            que.push({nx, ny});
        }
    }
    puts("-1");
}
int main()
{
//    freopen("data1.in", "r", stdin);
//    freopen("check1.out", "w", stdout);
    int t;
    scanf("%d", &t);
    while(t--){
        solve();
    }
    return 0;
}