©2020-2024 ioDraw All rights reserved
Problem Description
It's the annual Tangyuan Festival on Tangyuan planet , But the big devil came to take the Tangyuan princess Σ( ° △ °|||)︴
As a knight of glutinous rice balls QAQ Konjac naturally shoulders the mission of saving tangyuan
QAQ Konjac has experienced many hardships （ did not ） after , Come to the great devil's castle , According to intelligence , Princess Tangyuan was put in the castle by the devil , then QAQ Konjac finds itself a way
Idiot , Fortunately, he got the map of the devil's castle , And I marked myself and Princess Tangyuan on it , So here comes the question... , Smart, can you help him figure out how many units he needs
Is it time to get to Princess Tangyuan ?
Ps：QAQ Konjac can move to adjacent non wall lattices each time , Every move costs money 1 Unit time
A lattice with a common edge is defined as adjacent
Input
Start with an integer T There are representatives T Group data
The first line of each set of test data has two integers n,m (2<=n,m<=300)
Next n That's ok m Labyrinth listed as the great devil , among
’#’ For the wall ,‘_‘ For the ground
A representative QAQ Konnyaku ,O For Princess Tangyuan :
Output
A set of data outputs an integer representing the QAQ The shortest time from konjaku to Tangyuan
If QAQ Konjac can not reach the position of tangyuan , output -1
Example Input
2 3 3 __A _## __O 2 2 A# #O
Example Output
6 -1
Hint
Author
QAsQ
#include<stdio.h> #include<string.h> #include<stdlib.h> int jx[] = {0, 1, 0,
-1}; int jy[] = {1, 0, -1, 0}; char map[3333][3333]; int visit[3333][3333];
struct node { int x, y, c; }q[99999], t, f; void bfs(int x, int y, int n, int
m) { int s = 0, e = 0, i; t.x = x; t.y = y; t.c = 0;// Because you put her in the q[e++] = t
I changed it because of it n second visit[t.x][t.y] = 1; q[e++] = t; while(s < e) { t = q[s++];
if(map[t.x][t.y] == 'O') { printf("%d\n", t.c); return; } for(i = 0; i < 4;
i++) { f.x = t.x + jx[i]; f.y = t.y + jy[i]; if(f.x >= 0 && f.x < n && f.y >= 0
&& f.y < m && !visit[f.x][f.y] && map[f.x][f.y] != '#') { f.c = t.c + 1;
visit[f.x][f.y] = 1; q[e++] = f; } } } printf("-1\n"); } int main() { int n, m,
t, i, j; scanf("%d", &t); while(t--) { memset(map, 0, sizeof(map));
memset(visit, 0, sizeof(visit)); scanf("%d%d", &n, &m); for(i = 0; i < n; i++)
{ scanf("%s", map[i]); } for(i = 0; i < n; i++) { for(j = 0; j < m; j++) {
if(map[i][j] == 'A') { break; } } if(j != m) break; } bfs(i, j, n, m); } return
0; }
Technology