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: Accepted
Take time: 0ms
Take Memory: 164KB
Submit time: 2017-02-15 20:13:06
****************************************************/

/***************************************************
User name: jk160505徐紅博
Result: Accepted
Take time: 4ms
Take Memory: 612KB
Submit time: 2017-02-15 21:33:25
****************************************************/

0 個評論

要回覆文章請先登錄註冊