现在的位置: 首页 > 综合 > 正文

2534: The Hero Rescued The Princess 用的是queue

2013年08月21日 ⁄ 综合 ⁄ 共 1732字 ⁄ 字号 评论关闭

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int maze[15][30];
int moves[4][2]={{0,1},{0,-1},{-1,0},{1,0}};
int bx,by,ex,ey;
int visited[15][30];
int n;
int main()
{
    scanf("%d",&n);
    int i,j;
    char c;
    int cx,cy;
    int s;
    bool flag;
    while (n--)
    {
        for (i=0;i<15;i++)
        {
            for (j=0;j<30;j++)
            {
                while(c=getchar(),c=='/n');
                switch (c)
                {
                    case '#':maze[i][j]=0;break;
                    case '.':maze[i][j]=1;break;
                    case 'M':maze[i][j]=2;break;
                    case 'T':ex=i;ey=j;maze[i][j]=1;break;
                    case 'S':bx=i;by=j;maze[i][j]=0;break;
                }
            }
        }
        memset(visited,0,sizeof(visited));
        queue<int> sq;
        visited[bx][by]=1;
        sq.push(bx);
        sq.push(by);
        flag=false;
        while (!sq.empty())
        {
            cx=sq.front();
            sq.pop();
            cy=sq.front();
            sq.pop();
            s=visited[cx][cy];
   if (maze[cx][cy]==2)
   {
    maze[cx][cy]=1;
    sq.push(cx);
    sq.push(cy);
    visited[cx][cy]++;
    continue;
   }
            for (i=0;i<4;i++)
            {
                cx+=moves[i][0];
                cy+=moves[i][1];
                if ((cx==ex)&&(cy==ey))
                {
                    printf("%d/n",s);
                    flag=true;
                    break;
                }
                if (maze[cx][cy]&&!visited[cx][cy])
                {
                    visited[cx][cy]=s+1;
                    sq.push(cx);
                    sq.push(cy);
                }
                cx-=moves[i][0];
                cy-=moves[i][1];
            }
            if ((cx==ex)&&(cy==ey))
               break;
        }
        if (!flag) puts("-1");
    }
    return 0;
}

抱歉!评论已关闭.