1. Problem Description
You are given an M × N matrix whose elements are either 0 or 1. Infact, most of the elements in this
matrix are 1. You are given the indices of an element (p,q) which is 1. Find the nearest 0 to it. Assume
that from an element all its 8 neighbours (including diagonal) are at the same distance. Use the
appropriate data structure. You are allowed to change the values of the matrix if needed.
Input Format:
M N Next M Lines: The matrix represented by 0/1’s Final Line: Point of interest, p q
Output Format:
as described
Sample Input
54 1111 1111 1111 0111 1101 12
Sample Output:
30
2. Problem Description
Given two vessels, one of which can accommodate a litres of water and the other - b litres of water,
determine the number of steps required to obtain exactly c litres of water in one of the vessels.
At the beginning both vessels are empty. The following operations are counted as ’steps’:
• emptying a vessel
• filling a vessel
• pouring water from one vessel to the other, without spilling, until one of the vessels is either
full or empty
Input Format:
An integer t, 1 = t = 100, denoting the number of testcases, followed by t sets of input data, each
consisting of three positive integers a, b, c not larger than 40000, given in separate lines.
Output Format:
For each set of input data, output the minimum number of steps required to obtain c litres, or -1 if this
is impossible.
Sample Input
2
5
2
3
2
3
4
Sample Output:
2
-1
Taken from http://www.spoj.pl/problems/POUR1/