Question 1
Problem
Consider a grid map of size m×n. The origin (0, 0) is taken as the top-left corner. The X axis is the vertical axis, the Y axis is the horizontal axis. A cell 0 denotes obstacle-free region, -1 denotes obstacles, and 1 denotes a gem. Given a source, the aim of the agent is to go to the gem. The step cost is the time. The agent moves 1 block distance per second (or √2 time for diagonal moves). The order of preference of actions is: E, SE, S, SW, W, NW, N, NE, where N, E, S, W stand for North, East, South and West respectively. The priority queue should be implemented such that, in case of a tie, a node that is inserted first should be removed first. Print the path from the source to the gem. Print only -1 if no path exists.
The input is t, the number of test cases, followed by (for every test case) m and n. The next m lines of n integers each denote the grid map. The next line contains the source indicated by two integers Sx Sy. The output is the path.
15 14 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 -1 0 0 0 0 0 0 0 0 0 0 0 -1 -1 0 0 0 0 0 -1 -1 0 0 0 0 0 0 0 0 0 0 0 -1 -1 0 0 -1 -1 0 0 1 0 0 0 0 0 0 0 0 -1 -1 -1 0 0 0 0 -1 -1 0 0 0 0 -1 -1 -1 0 0 0 0 -1 -1 0 0 0 0 -1 -1 0 0 0 -1 -1 0 0 0 0 0 0 0 0 0 0 0 -1 -1 0 0 0 0 0 0 0 0 -1 -1 0 -1 -1 0 0 0 0 0 0 0 0 -1 -1 0 0 0 0 -1 -1 -1 0 0 0 0 0 0 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 9 13 11 0 -1 -1 0 0 0 0 0 0 0 0 0 -1 -1 0 0 0 0 0 0 0 0 0 -1 -1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 -1 0 -1 -1 -1 -1 -1 0 0 0 0 0 0 -1 -1 -1 -1 -1 -1 0 0 0 0 -1 -1 -1 0 -1 -1 -1 0 0 0 0 -1 -1 -1 0 0 -1 -1 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 -1 -1 -1 -1 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 10 12 0 1 -1 0 -1 -1 0 0 -1 0 0 0 0 0 -1 -1 -1 -1 0 0 -1 0 0 0 0 -1 -1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 -1 0 0 0 0 -1 0 0 0 0 0 -1 -1 0 0 0 0 -1 0 0 0 -1 -1 0 0 0 0 0 0 0 0 0 -1 0 0 -1 0 0 0 0 -1 -1 0 0 -1 0 0 -1 0 -1 -1 0 -1 -1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 2 10 10 10 -1 -1 0 0 0 0 0 0 0 0 -1 -1 0 0 0 0 0 -1 -1 0 0 0 -1 0 0 0 0 -1 -1 0 0 0 -1 -1 0 0 0 0 0 0 0 0 0 -1 -1 0 0 -1 -1 0 0 0 0 -1 -1 -1 -1 -1 -1 0 0 -1 0 0 0 -1 -1 0 0 0 0 0 0 0 0 0 -1 0 0 1 0 -1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 1 14 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 -1 -1 0 0 0 0 0 0 0 0 0 0 -1 -1 -1 0 0 0 0 -1 -1 -1 0 0 0 -1 -1 -1 0 0 0 0 -1 -1 -1 0 0 0 0 0 0 0 0 0 0 -1 -1 -1 0 0 0 0 0 -1 -1 -1 0 0 -1 -1 -1 0 0 0 0 0 -1 -1 -1 0 -1 -1 0 0 0 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 0 0 0 -1 -1 -1 0 0 0 -1 -1 -1 0 0 0 0 -1 -1 -1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 10 10 0 0 0 -1 -1 0 0 0 0 0 0 -1 -1 -1 -1 0 0 -1 -1 0 0 0 0 0 0 0 0 0 0 0 -1 -1 0 0 0 -1 -1 0 0 0 -1 -1 0 0 0 -1 -1 0 0 0 -1 -1 -1 -1 0 -1 -1 0 0 0 1 -1 -1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 9 10 11 0 0 0 -1 -1 0 0 0 0 -1 0 0 0 -1 -1 0 0 -1 -1 0 -1 0 0 0 -1 -1 0 0 0 0 0 0 0 0 -1 -1 -1 0 0 0 -1 -1 0 0 -1 -1 -1 -1 0 0 0 -1 -1 0 0 -1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 -1 -1 0 0 0 0 -1 0 -1 0 0 -1 -1 0 0 0 0 -1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 6 0 12 12 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 -1 -1 0 0 0 0 0 0 0 -1 -1 0 -1 -1 0 0 0 0 0 0 0 -1 -1 0 -1 -1 0 0 0 -1 -1 -1 0 0 0 0 -1 -1 0 0 0 -1 -1 -1 -1 0 0 0 -1 -1 0 0 0 0 0 -1 -1 0 0 0 0 -1 -1 -1 0 0 0 0 0 0 0 0 0 -1 -1 -1 0 0 1 0 0 0 0 -1 -1 -1 -1 -1 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 11 11 10 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 -1 -1 -1 0 0 -1 -1 0 0 0 0 -1 -1 0 0 0 -1 -1 0 0 -1 0 0 0 0 0 0 -1 -1 -1 -1 -1 0 0 0 0 0 0 0 0 0 -1 -1 -1 0 0 0 0 0 0 0 -1 -1 -1 0 0 -1 -1 0 0 0 0 0 1 0 0 0 0 -1 -1 0 0 0 0 0 0 0 0 -1 -1 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 8 0 11 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 -1 0 0 0 -1 -1 0 0 0 0 0 0 0 -1 -1 0 0 0 -1 -1 1 0 0 0 0 -1 -1 0 0 -1 -1 -1 -1 -1 -1 0 -1 0 0 -1 -1 0 0 0 0 -1 -1 -1 0 -1 -1 0 0 0 -1 0 0 0 0 0 0 0 0 -1 -1 0 -1 -1 -1 0 0 0 0 0 0 0 0 -1 -1 0 -1 0 0 0 0 0 -1 -1 0 0 0 0 0 0 0 0 0 0 0 0 -1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 5 12 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 -1 -1 0 0 0 0 0 0 0 0 0 0 0 -1 -1 -1 1 0 0 0 0 0 0 0 0 0 0 -1 -1 -1 0 0 0 0 -1 -1 -1 0 0 0 0 0 -1 -1 -1 0 0 0 -1 -1 -1 0 0 0 0 0 -1 -1 -1 0 0 0 0 -1 -1 0 0 0 0 0 0 -1 -1 0 -1 -1 -1 0 0 0 0 0 0 0 0 -1 -1 0 -1 -1 -1 0 0 0 0 0 0 0 0 -1 -1 0 0 0 0 -1 -1 0 0 0 0 0 0 0 0 0 0 0 0 -1 -1 -1 0 0 0 0 0 0 0 0 0 0 0 -1 -1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 11 11 13 11 -1 -1 -1 0 0 0 0 0 0 -1 0 -1 -1 -1 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 -1 0 0 0 -1 -1 0 0 0 0 -1 -1 0 -1 -1 -1 -1 0 0 0 0 0 0 -1 -1 -1 -1 -1 0 0 0 0 0 -1 -1 -1 -1 0 0 0 0 0 0 0 -1 -1 -1 0 0 0 0 0 0 0 0 -1 -1 -1 0 0 0 0 0 0 0 0 0 -1 -1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 2 5 11 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 -1 -1 -1 -1 0 -1 -1 0 -1 -1 0 -1 0 0 -1 -1 -1 0 0 -1 -1 0 -1 -1 0 0 0 0 0 0 0 0 0 0 0 0 -1 -1 -1 -1 -1 0 -1 -1 0 0 0 0 0 0 -1 -1 -1 -1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 -1 0 0 0 0 0 0 -1 0 0 0 0 0 0 -1 0 0 0 0 0 0 -1 0 -1 -1 0 0 0 -1 0 0 0 1 0 -1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 11 10 0 0 0 0 -1 0 -1 -1 -1 0 0 0 0 0 -1 0 0 0 -1 0 0 0 0 0 0 -1 -1 0 -1 0 0 1 0 0 0 -1 -1 0 -1 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 -1 -1 0 0 0 0 -1 0 0 -1 -1 -1 0 0 0 0 0 0 0 -1 0 -1 -1 0 0 0 0 0 -1 -1 0 -1 -1 0 0 0 0 0 -1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 9 10 10 -1 0 0 0 -1 0 0 -1 -1 0 0 0 0 1 -1 0 -1 -1 -1 0 0 0 0 0 0 0 -1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 -1 0 0 0 -1 -1 0 0 0 -1 -1 0 0 0 -1 -1 0 0 0 -1 -1 -1 0 0 0 0 0 0 0 0 -1 -1 -1 0 0 0 0 0 0 0 -1 -1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 9
13 9 13 8 13 7 13 6 12 5 11 5 10 5 9 5 8 5 7 5 6 5 5 5 4 5 0 0 1 0 2 0 3 1 3 2 3 3 3 4 3 5 3 6 4 7 5 8 6 8 7 8 8 8 9 8 10 9 11 10 2 10 2 9 2 8 2 7 2 6 2 5 2 4 3 3 3 2 3 1 2 0 1 0 0 1 7 1 7 2 7 3 7 4 7 5 8 6 8 7 8 8 7 9 4 0 5 0 6 0 7 0 8 1 9 2 10 3 11 4 11 5 12 6 12 7 12 8 12 9 12 10 12 11 12 12 8 9 8 8 8 7 8 6 8 5 8 4 8 3 8 2 7 1 6 0 6 0 6 1 6 2 6 3 7 4 8 5 8 6 8 7 8 8 8 9 4 11 5 11 6 11 7 11 8 11 9 10 9 9 9 8 9 7 9 6 9 5 9 4 9 3 9 2 8 1 8 0 8 1 8 2 7 3 7 4 7 5 7 6 7 7 7 8 10 5 9 5 8 5 7 5 6 6 6 7 6 8 5 9 4 10 3 11 2 10 11 11 11 10 10 9 9 8 8 7 7 6 6 6 5 6 4 6 3 6 2 5 2 5 2 6 2 7 3 8 4 9 5 10 6 10 7 10 8 10 9 10 10 9 11 8 1 2 1 3 2 4 3 4 4 4 5 4 6 4 7 4 8 5 9 6 5 9 4 8 3 7 2 7 1 6 1 5 2 4 2 3 2 2 3 1 9 9 8 8 7 7 6 6 5 5 4 5 3 5 2 4 1 3
Time Limit: 10
Memory Limit: 256
Source Limit:
