- 2020-08-06 03:33
*views 4*- c language
- chart

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

- Flow Chart77 blogs
- Java38 blogs
- Python30 blogs
- MySQL16 blogs
- Linux16 blogs
- Android15 blogs
- Administration13 blogs
- Database12 blogs
- more...

Daily Recommendation

©2020 ioDraw All rights reserved

Self made whole person computer program PHP call shell command python Simple record of network programming layui.table Examples of dynamically getting header and list data Big data environment --- data warehouse (hive+mysql+hadoop) The construction of What are the types of variables ?MYSQL database DML Common commands 《 From machine learning to deep learning 》 note （2） Unsupervised learning log4j Method of printing exception stack information Android Development — Display food information according to customer budget