HOJ 2979 Escape from Pyramids -BFS求最小的步数

HOJ 2979 Escape from Pyramids --------BFS求最小的步数

HOJ 2979 Escape from Pyramids

#include <iostream>#include <stdio.h>#include <cstring>#include <queue>using namespace std;bool vis[101][101];char map[101][101];int dx[]= {-1,-1,0,0,1,1};int dy[]= {-1,0,-1,1,0,1};int T,n;struct point{    int x,y,t;};int main(){    char c;    int cases=1;    int tmp=0;    while(scanf("%d%d",&n,&T)==2)    {        if(tmp==1)  printf("\n");        tmp=1;        memset(vis,false,sizeof(vis));        point start;        queue<point> v;        for(int i=1; i<=n; i++)        {            for(int j=1; j<=i; j++)            {                scanf(" %c",&c);                map[i][j]=c;                if(c=='S')                {                    start.x=i;                    start.y=j;                    start.t=0;                    vis[i][j]=true;                }            }        }        v.push(start);        int ans=10000000;        while(!v.empty())        {            point cur,pre;            pre=v.front();            if(map[pre.x][pre.y]=='D')            {                ans=pre.t;                break;            }            v.pop();            for(int i=0; i<6; i++)            {                cur.x=pre.x+dx[i];                cur.y=pre.y+dy[i];                if(cur.x>0&&cur.x<=n&&cur.y>0&&cur.y<=cur.x&&!vis[cur.x][cur.y]&&map[cur.x][cur.y]!='*')                {                    cur.t=pre.t+1;                    vis[cur.x][cur.y]=true;                    v.push(cur);                }            }        }        printf("Maze #%d :\n",cases++);        if(ans>T) printf("Oh No, I'm afraid that you don't have enough time to escape!\n");        else if(ans==1)   printf("Hurry up, You need 1 minute to escape!\n");        else printf("Hurry up, You need %d minutes to escape!\n",ans);    }    return 0;}