The total time limit: 1000 ms memory limit: 65536 KB
description
The princess had been seized by the wicked being held somewhere in his cell, the cell with N * M (N, M & lt;=200) of matrix, the matrix of each can represent road (@), wall (#), and the guards (x),
Brave knights (r) decided to alone to save the princess (a), we assume that the rescue success said is "knight reached where the princess", because in the path to where the princess might encounter guards, knight once encountered guards, must kill the guards before you can move on,
Now suppose knights can up, down, left and right four direction, every mobile location need 1 unit time, killing a guard takes an additional 1 unit time, at the same time assume that knight enough strong, has the ability to kill all the guards,

A given cell matrix, the princess and knight guard in place in the matrix, would you please calculate rescue success takes the shortest time,

enter
An integer S first behavior, according to input data on the number of groups (multiple input)
Then there are S set of data, each group of data according to the following format input
1, two integer N and M, (N, M & lt;=200).
2, then N lines, each line has M characters, "@" on behalf of the road, "a" on behalf of the princess, "r" on behalf of the knight, "x" on behalf of the guards, "#" is for the walls,
o
If rescue operation is successful, the output an integer, said the action of the shortest time,
If Impossible, output "Impossible"
sample input

sample output
13
7

I used the memory search, can work out the first example, but not ac, bosses see which problems

 # include 
#include 
#include 
using namespace std; 

Int s; 
Int n, m; 
Char mg [210] [210];//a maze 
Int v [210] [210];//to judge array 
Int rx and ry;//start 
Int dx [4]={0, 0, 1, 1}; 
Int dy [4]={1, 1, 0, 0}; 
Int ds [210] [210];//to the finish line at some point the smallest distance 

Int DFS (int x, int y) {
If [x] [y] (ds) return the ds [x] [y]; 
If (mg [x] [y]=='a') return 0; 
Int temp=1 & lt; <30; 
for(int i=0; I & lt; 4. I++) {
Int the x1=x + dx [I]; 
Int y1=y + dy [I]; 
if(! V [x1] [y1]) {
If (mg [x1] [y1]=='#') continue; 
The else {
V [x1] [y1]=1; 
Temp=min (temp, DFS (x1, y1)); 
V [x1] [y1]=0; 
} 
} 
} 
If (mg [x] [y]=='x') ds [x] [y]=temp + 2; 
The else ds [x] [y]=temp + 1; 
Return the ds [x] [y]; 
} 

Int main () {
Cin & gt;> s; 
While (s -) {
Cin & gt;> N & gt;> m; 
Memset (mg, '#', sizeof (mg)); 
Memset (v, 0, sizeof (v)); 
Memset (ds, 0, sizeof (ds)); 
for(int i=1; I & lt;=n; I++) {
For (int j=1; J & lt;=m; J++) {
Cin & gt;> Mg [I] [j]; 
If (mg [I] [j]=='r') {
Rx=I; 
Ry=j; 
} 
} 
} 
V (rx) [ry]=1; 
Int ans=DFS (rx and ry); 
If (ans & gt;=1 & lt; <30) cout & lt; <"Impossible" & lt; The else cout & lt; } 
return 0; 
} 

CodePudding user response:

Shortest path is BFS, use queue structure
Use DFS will continue to search, use the system in the stack, iterate through all the results back, otherwise you cannot consider you reach is one of the shortest path, can only prove that reached

CodePudding user response:

Fun

reference 1 floor response:

shortest path is BFS, use queue structure
Use DFS will continue to search, use the system in the stack, iterate through all the results back, otherwise you cannot consider you reach is one of the shortest path, can only prove that reached

BFS and priority queue is the optimal method, the DFS I use an array of memory to the finish line at some point of the shortest path length, without array directly recursive will timeout

CodePudding user response:

Timeout is the algorithm itself.
Is not can't find the answer but not fast enough

In memory, the shortest path is not can't, starting from the target, in turn spreading around, write the shortest distance to target, until meet starting point, but this process is also BFS
Using DFS is still the same problem, do not do traverse don't know the optimal results