- 2020-08-06 03:33
*views 5*- 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 Chart79 blogs
- Python76 blogs
- Java72 blogs
- Vue41 blogs
- MySQL25 blogs
- Linux21 blogs
- javascript19 blogs
- Mind map18 blogs
- more...

Daily Recommendation

views 9

views 6

views 6

views 5

views 4

©2020 ioDraw All rights reserved

Laravel HomesteadVue Novice ： The front end of file preview function python-- Freshman final test questions （ With answers ）C# Time every day 00 spot 00 branch 00 Second auto restart software This article takes you to explain the working principle of matrix keyboard springboot+vue+shiro Function authority Mining virus processing record Vue Export page as PDF file @ControllerAdvice Intercept abnormal return data 10000 R & D personnel ! Huawei's world's first car size lidar 150 M detection range