Pixels in the unique path
You are provided with a grid of pixels and the task is to reach from the first pixel inside the grid to the last pixel. There exists a unique path between the first and the last pixels. The task is to list out the pixel numbers that are being traversed. One is allowed to move in four directions as is shown in Fig. 1, if a connection is available. Write an algorithm to generate the only existing path.
Mirror Center
Fig.1 - The allowed four directions.
For example, let there be a 5×8 grid and we have to start from pixel number 1. All the pixels are numbered in row-wise manner starting from ‘1’, as is shown in Fig. 2. The required sequences of pixels to be followed so as to reach the last pixel, i.e. 40 are marked in Fig. 2.
Mirror Center
Fig.2 - A 5×8 grid and the existing unique path.
You have to develop and implement the algorithm that will produce the path existing in between the first pixel and the last pixel.
Input:
Line 1 contains two space separated integers M and N, i.e. the size of the grid is M×N.
Following M×N lines contains space separated 5 numbers. The first is an integer, say i, representing a pixel number followed by a sequence of four bits (0/1) showing the directions one can move from pixel i. The order in which directions are considered in the given sequence of bits is same as shown in Fig. 1.
Output:
A single line output contains space separated pixel numbers that are to be followed to reach the last pixel from the first pixel.
Constraints :
All integers range in between 1 and 1000.
Sample Input:
5 8
1 0 1 1 0
2 0 1 1 1
3 0 1 0 1
4 0 0 1 1
5 0 1 1 0
6 0 1 1 1
7 0 1 0 1
8 0 0 1 1
9 1 1 1 0
10 1 0 0 1
11 0 1 0 0
12 1 0 1 1
13 1 0 1 0
14 1 1 0 0
15 0 0 1 1
16 1 0 1 0
17 1 0 1 0
18 0 1 1 0
19 0 1 0 1
20 1 0 1 1
21 1 0 1 0
22 0 1 1 0
23 1 0 0 1
24 1 0 0 0
25 1 0 1 0
26 1 1 0 0
27 0 0 1 1
28 1 0 1 0
29 1 0 1 0
30 1 0 1 0
31 0 1 1 0
32 0 0 1 1
33 1 1 0 0
34 0 0 0 1
35 1 0 0 0
36 1 1 0 0
37 1 0 0 1
38 1 1 0 0
39 0 1 0 1
40 1 0 0 1
Sample Output:
1 2 3 4 12 20 28 36 37 29 21 13 5 6 14 15 23 22 30 38 39 40
EXPLANATION:
The size of the grid is 5×8, i.e. 40 and pixels are numbered in row-wise manner starting from 1. Next 40 lines contain the direction information for each pixel. For example, from pixel number 1 you can move only in directions 2 and 3 (refer Fig. 1 for direction numbers) therefore bit numbers 1 and 4 are zero. Similarly, in case of pixel number 11, you can move only in direction 2 therefore single bit at the said position is set.
The output contains the pixel numbers to be followed to reach the last pixel from pixel number 1 (refer Fig. 2).