又到了汤圆星球一年一度的汤圆节了,但是大魔王却过来把汤圆公主抓走了Σ( ° △ °|||)︴
身为汤圆骑士的QAQ蒟蒻自然而然的肩负着拯救汤圆的使命
QAQ蒟蒻经历了千辛万苦(并没有)之后,来到了大魔王的城堡,根据情报,汤圆公主就被大魔王放在城堡内,然后QAQ蒟蒻发现自己是一个路
痴,所幸的是他拿到了大魔王的城堡的地图,而且在这上面标注了自己和汤圆公主的位置,那么问题来了,聪明的你能帮他计算出需要多少单位
的时间来赶到汤圆公主的位置吗?
Ps:QAQ蒟蒻每一次都可以移动到相邻的非墙的格子中,每次移动都要花费1个单位的时间
有公共边的格子定义为相邻
一开始为一个整数T代表一共有T组数据
每组测试数据的第一行有两个整数n,m (2<=n,m<=300)
接下来的n行m列为大魔王的迷宫,其中
’#’为墙壁,‘_‘为地面
A代表QAQ蒟蒻,O代表汤圆公主:
一组数据输出一个整数代表从QAQ蒟蒻到汤圆的位置的最短时间
如果QAQ蒟蒻不能到达汤圆的位置,输出-1
2 3 3 __A _## __O 2 2 A# #O
6 -1
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e2 + 5;
struct node {
int x, y, time;
};
int bx, by, ex, ey;
int graph[maxn][maxn];
bool visited[maxn][maxn];
int direction[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
void SR(int n, int m) {
for(int i = 1; i <= n; i++) {
getchar();
for(int j = 1; j <= m; j++) {
char c;
scanf("%c", &c);
if(c == 'A') {
bx = i;
by = j;
graph[i][j] = 1; //1代表能走 0 代表墙
} else if(c == 'O') {
ex = i;
ey = j;
graph[i][j] = 1;
} else if(c == '_') {
graph[i][j] = 1;
} else {
graph[i][j] = 0;
}
}
}
}
void BFS(int bx, int by, int n, int m) {
visited[bx][by] = 1;
struct node p, q;
queue<node> Q;
p.x = bx;
p.y = by;
p.time = 0;
Q.push(p);
while(!Q.empty()) {
p = Q.front();
Q.pop();
if(p.x == ex && p.y == ey) {
printf("%d\n", p.time);
return;
}
for(int i = 0; i < 4; i++) {
q.x = p.x + direction[i][0];
q.y = p.y + direction[i][1];//过于坑人 外面的if必须存在
if(q.x >= 1 && q.x <= n && q.y >= 1 && q.y <= m) {
if(!visited[q.x][q.y] && graph[q.x][q.y]) {
visited[q.x][q.y] = 1;
q.time = p.time + 1;
Q.push(q);
}
}
}
}
printf("-1\n");
}
int main() {
int T;
scanf("%d", &T);
while(T--) {
memset(visited, 0, sizeof(visited));
int n, m;
scanf("%d%d", &n, &m);
SR(n, m);
BFS(bx, by, n, m);
}
return 0;
}
/***************************************************
User name:
Result: Accepted
Take time: 16ms
Take Memory: 612KB
Submit time: 2018-01-30 19:53:14
****************************************************/