Data Structure 4


Submit solution

Points: 2
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
C++, Python3

Village of the Sorcerer

This practice problem will require you to utilise Queue to solve the reachability problem.

You are given a map for from the Village of the Sorcerer problems and the player's initial position. Your objective is to print out a map containing all the reachable points for that player.

Hint: please make sure you have completed csci125p014 before attempting this task.

For each step, the player can move in four directions: left, right, up, down. The following areas are not reachable (only exception being the player's initial position):

1. the player cannot stand on top of the fence.

2. the player may not move to any area where there is a house (any  
    part of the house, not just the original coordinate).

Input Specification

The first line will contain 3 integers \(K,N,M\) (\(1 < K,N,M < 20\)), where \(K\) is the number of test cases and \(N,M\) the dimension size.

What follows are \(K\) maps, each map occupies \(N\) lines, each line contains \(M\) integers, each the item at that coordinate. It is guaranteed that the player (denoted by \(4\)) will appear on the map, and only once.

Output Specification

The output should contain \(K\) maps, separated by an empty line.

Each map should be \(N\) lines, each line \(M\) binary numbers, with 0 being reachable, 1 being not reachable.

Sample Input

3 6 17
0 1 0 0 0 0 1 0 0 1 1 1 0 2 1 0 0
1 1 0 1 0 1 1 0 1 0 1 0 1 0 1 1 0
0 0 4 1 1 0 1 1 3 1 1 1 1 0 0 0 1
1 1 0 1 0 0 0 0 1 0 1 0 1 0 0 1 1
0 0 0 0 0 0 1 1 0 0 0 0 2 0 2 0 1
1 2 1 1 3 0 0 0 0 1 0 1 1 0 1 0 0

0 1 0 1 0 0 1 0 1 0 0 1 0 1 1 0 1
0 0 2 1 1 1 1 1 1 0 1 0 1 1 0 1 0
0 0 0 1 0 1 0 1 0 0 1 2 0 4 1 0 1
1 1 0 1 0 1 0 1 0 1 0 0 1 1 0 1 0
0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 2
1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 1 0

0 0 0 0 2 1 1 0 1 0 0 1 1 1 0 0 0
0 0 1 0 1 1 1 1 0 0 0 0 1 1 1 1 1
0 1 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0
0 0 0 0 0 0 1 0 1 1 0 0 1 0 0 0 1
1 1 1 0 0 0 4 0 0 0 0 0 0 1 0 0 0
0 1 1 1 0 0 0 1 0 1 0 0 1 3 0 1 1

Sample Output

0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 
0 0 1 0 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 0 0 0
0 0 1 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 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 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 0 0 0 0 0 0 0 0 1 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 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

1 1 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0
1 1 0 1 0 0 0 0 1 1 1 1 0 0 0 0 0
1 0 0 1 0 1 1 1 1 1 0 1 0 0 0 0 0
1 1 1 1 1 1 0 1 0 0 1 1 0 0 0 0 0
0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0
0 0 0 0 1 1 1 0 1 0 1 1 0 0 0 0 0

Comments

There are no comments at the moment.