Cerinta completa
Ron and Hermione are deep in the Forbidden Forest collecting potion ingredients, and they’ve managed to lose their way. The path out of the forest is blocked, so they must make their way to a portkey that will transport them back to Hogwarts.
Consider the forest as an grid. Each cell is either empty (represented by .) or blocked by a tree (represented by ). Ron and Hermione can move (together inside a single cell) LEFT, RIGHT, UP, and DOWN through empty cells, but they cannot travel through a tree cell. Their starting cell is marked with the character , and the cell with the portkey is marked with a . The upper-left corner is indexed as .
.X.X......X
.X*.X.XXX.X
.XX.X.XM...
......XXXX.
In example above, Ron and Hermione are located at index and the portkey is at . Each cell is indexed according to Matrix Conventions.
Hermione decides it’s time to find the portkey and leave. They start along the path and each time they have to choose a direction, she waves her wand and it points to the correct direction. Ron is betting that she will have to wave her wand exactly times. Can you determine if Ron’s guesses are correct?
The map from above has been redrawn with the path indicated as a series where is the starting point (no decision in this case), indicates a decision point and is just a step on the path:
.X.X.10000X
.X*0X0XXX0X
.XX0X0XM01.
...100XXXX.
There are three instances marked with where Hermione must use her wand.
Note: It is guaranteed that there is only one path from the starting location to the portkey.
Function Description
Complete the countLuck function in the editor below. It should return a string, either if Ron is correct or if he is not.
countLuck has the following parameters:
- matrix: a list of strings, each one represents a row of the matrix
- k: an integer that represents Ron’s guess
Input Format
The first line contains an integer , the number of test cases.
Each test case is described as follows:
The first line contains space-separated integers and , the number of forest matrix rows and columns.
Each of the next lines contains a string of length describing a row of the forest matrix.
The last line contains an integer , Ron’s guess as to how many times Hermione will wave her wand.
Constraints
- There will be exactly one and one in the forest.
- Exactly one path exists between and .
Output Format
On a new line for each test case, print if Ron impresses Hermione by guessing correctly. Otherwise, print .
Sample Input
3
2 3
*.M
.X.
1
4 11
.X.X......X
.X*.X.XXX.X
.XX.X.XM...
......XXXX.
3
4 11
.X.X......X
.X*.X.XXX.X
.XX.X.XM...
......XXXX.
4
Sample Output
Impressed
Impressed
Oops!
Explanation
For each test case, denotes the number of times Hermione waves her wand.
Case 0: Hermione waves her wand at , giving us . Because , we print on a new line.
Case 1: Hermione waves her wand at , , and , giving us . Because , we print on a new line.
Case 2: Hermione waves her wand at , , and , giving us . Because and , and we print on a new line.
Limbajul de programare folosit: java8
Cod:
import java.io.*;
import java.util.*;
class Pair {
int x, y;
Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
class State {
Pair p;
int counter;
State(Pair position) {
this.p = position;
this.counter = 0;
}
State(Pair position, int counter) {
this.p = position;
this.counter = counter;
}
}
public class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int q = sc.nextInt();
for (int i = 0; i < q; i++) {
int N = sc.nextInt();
int M = sc.nextInt();
Pair start = new Pair(0, 0), end = new Pair(0, 0);
int[][] board = new int[N][M];
for (int j = 0; j < N; j++) {
String line = sc.next();
for (int k = 0; k < M; k++) {
if (line.charAt(k) == 'X') {
board[j][k] = -1;
} else if (line.charAt(k) == 'M') {
board[j][k] = 0;
start = new Pair(j, k);
} else if (line.charAt(k) == '*') {
board[j][k] = 0;
end = new Pair(j, k);
}
}
}
int K = sc.nextInt();
// Solve problem here
LinkedList<State> queue = new LinkedList<State>();
queue.addFirst(new State(start));
while (queue.size() > 0) {
State current = queue.pollLast();
Pair p = current.p;
ArrayList<Pair> nextMove = new ArrayList<Pair>();
if (p.x == end.x && p.y == end.y) {
board[p.x][p.y] = current.counter;
break;
} else {
board[p.x][p.y] = -1;
}
// Right
if (p.y + 1 < M && board[p.x][p.y + 1] == 0) {
nextMove.add(new Pair(p.x, p.y + 1));
}
// Left
if (p.y - 1 >= 0 && board[p.x][p.y - 1] == 0) {
nextMove.add(new Pair(p.x, p.y - 1));
}
// Up
if (p.x - 1 >= 0 && board[p.x - 1][p.y] == 0) {
nextMove.add(new Pair(p.x - 1, p.y));
}
// Down
if (p.x + 1 < N && board[p.x + 1][p.y] == 0) {
nextMove.add(new Pair(p.x + 1, p.y));
}
if (nextMove.size() > 1) {
current.counter++;
}
for (int g = 0; g < nextMove.size(); g++) {
current.p = nextMove.get(g);
queue.addFirst(new State(new Pair(current.p.x, current.p.y), current.counter));
}
}
if (board[end.x][end.y] == K) {
System.out.println("Impressed");
} else {
System.out.println("Oops!");
}
}
}
}
Scor obtinut: 1.0
Submission ID: 464604132
Link challenge: https://www.hackerrank.com/challenges/count-luck/problem