sdutacm-汤圆の拯救计划

汤圆の拯救计划

Time Limit: 1000MSMemory Limit: 65536KB

SubmitStatistic

PRoblemDescription

又到了汤圆星球一年一度的汤圆节了，但是大魔王却过来把汤圆公主抓走了Σ( °△ °|||)︴身为汤圆骑士的QAQ蒟蒻自然而然的肩负着拯救汤圆的使命QAQ蒟蒻经历了千辛万苦（并没有）之后，来到了大魔王的城堡，根据情报，汤圆公主就被大魔王放在城堡内，然后QAQ蒟蒻发现自己是一个路痴，所幸的是他拿到了大魔王的城堡的地图，而且在这上面标注了自己和汤圆公主的位置，那么问题来了，聪明的你能帮他计算出需要多少单位的时间来赶到汤圆公主的位置吗？Ps：QAQ蒟蒻每一次都可以移动到相邻的非墙的格子中，每次移动都要花费1个单位的时间有公共边的格子定义为相邻

Input

一开始为一个整数T代表一共有T组数据每组测试数据的第一行有两个整数n,m (2<=n,m<=300)接下来的n行m列为大魔王的迷宫，其中’#’为墙壁，‘_‘为地面A代表QAQ蒟蒻，O代表汤圆公主:

Output

一组数据输出一个整数代表从QAQ蒟蒻到汤圆的位置的最短时间如果QAQ蒟蒻不能到达汤圆的位置，输出-1

ExampleInput

2
3 3
__A
_##
__O
2 2
A#
#O
ExampleOutput
6
-1
Hint
 
Author
QAsQ
#include <iostream>#include<bits/stdc++.h>using namespace std;char tu[306][306];int book[306][306];int n,m;int jx[] = {0,-1,0,1};int jy[] ={1,0,-1,0};struct node{    int x;    int y;    int ans;}q[300],t,f;void bfs(int x,int y){    int i;    //int s=0,e=0;    queue<node>g;    t.x = x;    t.y =y;    t.ans = 0;    g.push(t);    book[x][y] = 1;    while(!g.empty())    {        f = g.front();        g.pop();        if(tu[f.x][f.y]=='O')        {        printf("%d/n",f.ans);        return ;        }        for(i =0;i<4;++i)        {           t.x = f.x+jx[i];           t.y = f.y+jy[i];           if(t.x>=0&&t.x<n&&t.y>=0&&t.y<m&&tu[t.x][t.y]!='#'&&book[t.x][t.y]==0)           {           t.ans = f.ans+1;           g.push(t);           book[t.x][t.y] = 1;           }        }    }    printf("-1/n");    return ;}int main(){    int t;    scanf("%d",&t);    while(t--)    {  scanf("%d%d",&n,&m);        //memset(tu,0,sizeof(tu));        memset(book,0,sizeof(book));        for(int i=0;i<n;i++)        {            scanf("%*c%s",tu[i]);        }        int ff=0;        int i,j;        for( i=0;i<n;i++)        {        for( j=0;j<m;j++)        {            if(tu[i][j]=='A')            {            ff=1;            break;            }        }        if(ff) break;        }        bfs(i,j);    }    return 0;}/***************************************************User name: jk160505徐红博Result: AcceptedTake time: 0msTake Memory: 164KBSubmit time: 2017-02-15 20:13:06****************************************************//***************************************************User name: jk160505徐红博Result: AcceptedTake time: 4msTake Memory: 612KBSubmit time: 2017-02-15 21:33:25****************************************************/