poj 2215 bfs求最短路

背景：最短路典型bfs，竟然ML! 后来发现时vis数组标记的时机不对，我开始是把每一个位置把它从队列头调用的时候才标记为访问过！但这种依然是有重复的内容出现在队列中，应该在对每一个位置入队的时候就标记为访问过。

我的代码：

#include<set>
#include<stack>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define M 39
#define INF 0x3fffffff
#define LL long long int
using namespace std;
struct place{int x,y,z,count;}s,e,temp1,temp2;
int f,r,c,dir[6][3]={1,0,0,-1,0,0,0,1,0,0,-1,0,0,0,1,0,0,-1};
bool vis[M][M][M],diagram[M][M][M];

bool bfs(){
     queue<place> q;
     q.push(s);
     while(!q.empty()){
        temp1=q.front();
        vis[temp1.x][temp1.y][temp1.z]=1;
       #ifdef LOCAL
        printf("the size of queue :%d\n",q.size());
       #endif // LOCAL
        q.pop();
        if(temp1.x == e.x && temp1.y == e.y && temp1.z == e.z){return true;}
        for(int i=0;i < 6;i++){
            temp2.x=temp1.x+dir[i][0];
            temp2.y=temp1.y+dir[i][1];
            temp2.z=temp1.z+dir[i][2];
            temp2.count=temp1.count+1;
            if(temp2.x > 0 && temp2.x <= r && temp2.y > 0 && temp2.y <= c && temp2.z > 0 && temp2.z <= f && !vis[temp2.x][temp2.y][temp2.z] && diagram[temp2.x][temp2.y][temp2.z]){
                vis[temp2.x][temp2.y][temp2.z]=1;
                q.push(temp2);
               }
        }
     }
     return false;
}

int main(void){
    while(scanf("%d%d%d",&f,&r,&c),f*f+r*r+c*c){
        getchar();
        for(int i=1;i <= f;i++){
            for(int j=1;j <= r;j++){
                for(int k=1;k <= c;k++){
                    char c;
                    c=getchar();
                    if(c == 'S'){s.x=j;s.y=k;s.z=i;}
                    else if(c == 'E'){e.x=j;e.y=k;e.z=i;}
                    c == '#' ? diagram[j][k][i]=0 : diagram[j][k][i]=1;
                }
                getchar();
            }
            getchar();
        }
        memset(vis,0,sizeof(vis));
        s.count=0;
        if(!bfs()) printf("Trapped!\n");
        else printf("Escaped in %d minute(s).\n",temp1.count);
    }
    return 0;
}

poj 2215 bfs求最短路

原文：http://blog.csdn.net/jibancanyang/article/details/44632669