Count Luck


Problem Statement :


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 .Oops!.


Solution :



title-img 


                            Solution in C :

In  C  :






#include <stdio.h>

#define MAX 1000000001

long long a[200][200], zas[1000000][2];
long long t,i,j,k,l,v,n,m,k,ki,kj,si,sj,zac,kon;
char c[1000];


long long sus(long long ii, long long jj)
{
long long vv=0;

if(ii>0 && a[ii-1][jj] !=-1) vv++;
if(jj>0 && a[ii][jj-1] !=-1) vv++;
if(ii+1<n && a[ii+1][jj] !=-1) vv++;
if(jj+1<m && a[ii][jj+1] !=-1) vv++;

if(ii == ki && jj == kj) return 0;

return vv;
}

int main()
{

scanf("%lld",&t);

while(t) {
  t--;
//  t=0;
  
  scanf("%lld %lld\n",&n,&m);
  
  for(i=0;i<n;i++) 
     {
      scanf("%s\n",c);
    for(j=0;j<m;j++) 
    {  
      if(c[j] == '.') a[i][j] = 1000000;
      if(c[j] == 'X') a[i][j] = -1;
      if(c[j] == 'M') {a[i][j] = MAX;si = i; sj = j;}
      if(c[j] == '*') {a[i][j] = 0;ki = i; kj = j;}
     }  
   }
   scanf("%lld",&k);

zac = 0;
kon = 1;

zas[0][0] = ki;
zas[0][1] = kj;

//printf("%lld %lld %lld\n",n,m,k);

while(a[si][sj] == MAX)
  {
   i = zas[zac][0];
   j = zas[zac][1];
  
   zac++;
  
   if(i>0 && a[i-1][j] != -1 && a[i][j]+1 < a[i-1][j])
      {
      a[i-1][j] = a[i][j] + 1;
      zas[kon][0] = i-1;
      zas[kon][1] = j;  
      kon++;
      } 
  if(j>0 && a[i][j-1] != -1 && a[i][j]+1 < a[i][j-1])
      {
      a[i][j-1] = a[i][j] + 1;
      zas[kon][0] = i;
      zas[kon][1] = j-1;  
      kon++;
      } 

   if(i+1<n && a[i+1][j] != -1 && a[i][j]+1 < a[i+1][j])
      {
      a[i+1][j] = a[i][j] + 1;
      zas[kon][0] = i+1;
      zas[kon][1] = j;  
      kon++;
      } 
   if(j+1<m && a[i][j+1] != -1 && a[i][j]+1 < a[i][j+1])
      {
      a[i][j+1] = a[i][j] + 1;
      zas[kon][0] = i;
      zas[kon][1] = j+1;  
      kon++;
      }  
  }

//printf("%lld\n",a[si][sj]);

i = si;
j = sj;
v = 0;

if(sus(i,j) > 1) v++;

while(i!= ki || j != kj)
 {
   if(i>0 && a[i-1][j]+1 == a[i][j])
     {
     i--;
     if(sus(i,j)>2) v++;
     continue;
     }
   if(j>0 && a[i][j-1]+1 == a[i][j])
     {
     j--;
     if(sus(i,j)>2) v++;
     continue;
     }
  if(i+1<n && a[i+1][j]+1 == a[i][j])
     {
     i++;
     if(sus(i,j)>2) v++;
     continue;
     }
  if(j+1<m && a[i][j+1]+1 == a[i][j])
     {
     j++;
     if(sus(i,j)>2) v++;
     continue;
     }  
 }

//printf("%lld=v\n",v);

if(v == k) 
  printf("Impressed\n",v);
else 
  printf("Oops!\n");  


}


return 0;
}
                        


                        Solution in C++ :

In  C++  :






#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cstdio>
#include <vector>
#include <map>
#include <set>

using namespace std;

#define SIZE(A) (int((A).size()))
#define pb(A) push_back(A)
#define mp(A,B) make_pair(A,B)

const int fx[] = {0, 1, 0, -1}, fy[] = {1, 0, -1, 0};

int n, m;
int col;
int p[2000][2000];
char w[2000][2000];
char s[2000][2000];

void dfs(int x, int y) {
	w[x][y]=col;
	for (int i = 0; i < 4; i++) {
		int xx = x+fx[i], yy = y+fy[i];

		if (xx<0||yy<0||xx>=n||yy>=m||w[xx][yy]==col||s[xx][yy]=='X') continue;

		p[xx][yy] = (i+2)&3;
		dfs(xx, yy);
	}
}

int solve(int x, int y) {
	w[x][y] = ++col;
	for (int i = x, j = y; s[i][j]!='M';) {
		int v = p[i][j];
		i += fx[v]; j += fy[v];
		w[i][j] = col;
	}

	int amo=0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (w[i][j]==col) {
				if (s[i][j]=='*') continue;
				
				int add=0;

				for (int k = 0; k < 4; k++) {
					int xx = i+fx[k], yy=j+fy[k];
					if (xx<0||yy<0||xx>=n||yy>=m||w[xx][yy]==col||s[xx][yy]=='X') continue;
					add=1;
				}

				amo+=add;
			}
		}
	}
	return amo;
}

int main() {
	int t;
	cin >> t;
	for (; t--;) {
		cin >> n >> m;
		for (int i = 0; i < n; i++) {
			scanf("%s", s[i]);
		}
		int k;
		cin >> k;

		col++;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (s[i][j] == 'M') {
					dfs(i, j);
				}
			}
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (s[i][j] == '*') {
					k -= solve(i, j);
				}
			}
		}
		puts(!k?"Impressed":"Oops!");
	}

    return 0;
}
                    


                        Solution in Java :

In  Java  :







import java.io.*;
import java.math.*;
import java.util.*;

import static java.util.Arrays.*;

public class Solution {
	private static final int mod = (int)1e9+7;

	final Random random = new Random(0);
	final IOFast io = new IOFast();

	/// MAIN CODE
	int w, h;
	char[][] cs;
	int[] dx = new int[] { 1, 0, -1, 0, };
	int[] dy = new int[] { 0, -1, 0, 1, };
	int dfs(int v, int p) {
		if(cs[v/w][v%w] == '*') return 0;
		int ret = -1;
		int move = 0;
		for(int i = 0; i < 4; i++) {
			final int y = v / w + dy[i];
			final int x = v % w + dx[i];
			if(x < 0 || y < 0 || x >= w || y >= h || cs[y][x] == 'X' || y*w+x == p) continue;
			move++;
			ret = Math.max(ret, dfs(y*w+x, v));
		}
		if(ret == -1) return -1;
		return ret + (move>1?1:0);
	}
	public void run() throws IOException {
		int TEST_CASE = Integer.parseInt(new String(io.nextLine()).trim());
//		int TEST_CASE = 1;
		while(TEST_CASE-- != 0) {
			h = io.nextInt();
			w = io.nextInt();
			cs = new char[h][];
			int cur = -1;
			for(int i = 0; i < h; i++) {
				cs[i] = io.next();
				for(int j = 0; j < w; j++) {
					if(cs[i][j] == 'M') cur = i*w+j;
				}
			}
			int K = io.nextInt();
			
			io.out.println(K == dfs(cur, -1) ? "Impressed" : "Oops!");
		}
	}
	

	/// TEMPLATE
	static int gcd(int n, int r) { return r == 0 ? n : gcd(r, n%r); }
	static long gcd(long n, long r) { return r == 0 ? n : gcd(r, n%r); }
	
	static <T> void swap(T[] x, int i, int j) {
		T t = x[i];
		x[i] = x[j];
		x[j] = t;
	}
	
	static void swap(int[] x, int i, int j) {
		int t = x[i];
		x[i] = x[j];
		x[j] = t;
	}
	

	static void radixSort(int[] xs) {
		int[] cnt = new int[(1<<16)+1];
		int[] ys = new int[xs.length];
		
		for(int j = 0; j <= 16; j += 16) {
			Arrays.fill(cnt, 0);
			for(int x : xs) { cnt[(x>>j&0xFFFF)+1]++; }
			for(int i = 1; i < cnt.length; i++) { cnt[i] += cnt[i-1]; }
			for(int x : xs) { ys[cnt[x>>j&0xFFFF]++] = x; }
			{ final int[] t = xs; xs = ys; ys = t; }
		}
	}
	
	static void radixSort(long[] xs) {
		int[] cnt = new int[(1<<16)+1];
		long[] ys = new long[xs.length];
		
		for(int j = 0; j <= 48; j += 16) {
			Arrays.fill(cnt, 0);
			for(long x : xs) { cnt[(int)(x>>j&0xFFFF)+1]++; }
			for(int i = 1; i < cnt.length; i++) { cnt[i] += cnt[i-1]; }
			for(long x : xs) { ys[cnt[(int)(x>>j&0xFFFF)]++] = x; }
			{ final long[] t = xs; xs = ys; ys = t; }
		}
	}
	

	static void arrayIntSort(int[][] x, int... keys) {
		Arrays.sort(x, new ArrayIntsComparator(keys));
	}
	
	static class ArrayIntsComparator implements Comparator<int[]> {
		final int[] KEY;
		
		public ArrayIntsComparator(int... key) {
			KEY = key;
		}
		
		@Override
		public int compare(int[] o1, int[] o2) {
			for(int k : KEY) if(o1[k] != o2[k]) return o1[k] - o2[k];
			return 0;
		}
	}
	
	static class ArrayIntComparator implements Comparator<int[]> {
		final int KEY;
		
		public ArrayIntComparator(int key) {
			KEY = key;
		}
		
		@Override
		public int compare(int[] o1, int[] o2) {
			return o1[KEY] - o2[KEY];
		}
	}
	
	
	void main() throws IOException {
		//		IOFast.setFileIO("rle-size.in", "rle-size.out");
		try {
			run();
		}
		catch (EndOfFileRuntimeException e) { }
		io.out.flush();
	}

	public static void main(String[] args) throws IOException {
		new Solution().main();
	}
	
	static class EndOfFileRuntimeException extends RuntimeException {
		private static final long serialVersionUID = -8565341110209207657L; }

	static
	public class IOFast {
		private BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		private PrintWriter out = new PrintWriter(System.out);

		void setFileIO(String ins, String outs) throws IOException {
			out.flush();
			out.close();
			in.close();
			in = new BufferedReader(new FileReader(ins));
			out = new PrintWriter(new FileWriter(outs));
			System.err.println("reading from " + ins);
		}

		//		private static final int BUFFER_SIZE = 50 * 200000;
		private static int pos, readLen;
		private static final char[] buffer = new char[1024 * 8];
		private static char[] str = new char[500*8*2];
		private static boolean[] isDigit = new boolean[256];
		private static boolean[] isSpace = new boolean[256];
		private static boolean[] isLineSep = new boolean[256];

		static {
			for(int i = 0; i < 10; i++) { isDigit['0' + i] = true; }
			isDigit['-'] = true;
			isSpace[' '] = isSpace['\r'] = isSpace['\n'] = isSpace['\t'] = true;
			isLineSep['\r'] = isLineSep['\n'] = true;
		}

		public int read() throws IOException {
			if(pos >= readLen) {
				pos = 0;
				readLen = in.read(buffer);
				if(readLen <= 0) { throw new EndOfFileRuntimeException(); }
			}
			return buffer[pos++];
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(nextString());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(nextString());
		}

		public char nextChar() throws IOException {
			while(true) {
				final int c = read();
				if(!isSpace[c]) { return (char)c; }
			}
		}
		
		int reads(int len, boolean[] accept) throws IOException {
			try {
				while(true) {
					final int c = read();
					if(accept[c]) { break; }
					
					if(str.length == len) {
						char[] rep = new char[str.length * 3 / 2];
						System.arraycopy(str, 0, rep, 0, str.length);
						str = rep;
					}
					
					str[len++] = (char)c;
				}
			}
			catch(EndOfFileRuntimeException e) { ; }
			
			return len;
		}
		
		int reads(char[] cs, int len, boolean[] accept) throws IOException {
			try {
				while(true) {
					final int c = read();
					if(accept[c]) { break; }
					cs[len++] = (char)c;
				}
			}
			catch(EndOfFileRuntimeException e) { ; }
			
			return len;
		}

		public char[] nextLine() throws IOException {
			int len = 0;
			str[len++] = nextChar();
			len = reads(len, isLineSep);
			
			try {
				if(str[len-1] == '\r') { len--; read(); }
			}
			catch(EndOfFileRuntimeException e) { ; }
			
			return Arrays.copyOf(str, len);
		}

		public String nextString() throws IOException {
			return new String(next());
		}

		public char[] next() throws IOException {
			int len = 0;
			str[len++] = nextChar();
			len = reads(len, isSpace);
			return Arrays.copyOf(str, len);
		}

		public int next(char[] cs) throws IOException {
			int len = 0;
			cs[len++] = nextChar();
			len = reads(cs, len, isSpace);
			return len;
		}

		public double nextDouble() throws IOException {
			return Double.parseDouble(nextString());
		}

		public long[] nextLongArray(final int n) throws IOException {
			final long[] res = new long[n];
			for(int i = 0; i < n; i++) {
				res[i] = nextLong();
			}
			return res;
		}

		public int[] nextIntArray(final int n) throws IOException {
			final int[] res = new int[n];
			for(int i = 0; i < n; i++) {
				res[i] = nextInt();
			}
			return res;
		}

		public int[][] nextIntArray2D(final int n, final int k) throws IOException {
			final int[][] res = new int[n][];
			for(int i = 0; i < n; i++) {
				res[i] = nextIntArray(k);
			}
			return res;
		}

		public int[][] nextIntArray2DWithIndex(final int n, final int k) throws IOException {
			final int[][] res = new int[n][k+1];
			for(int i = 0; i < n; i++) {
				for(int j = 0; j < k; j++) {
					res[i][j] = nextInt();
				}
				res[i][k] = i;
			}
			return res;
		}

		public double[] nextDoubleArray(final int n) throws IOException {
			final double[] res = new double[n];
			for(int i = 0; i < n; i++) {
				res[i] = nextDouble();
			}
			return res;
		}

	}

}
                    


                        Solution in Python : 
                            
In   Python3  :









T = int(input()) # num test cases

def find(matrix, char):
    char_row = [row for row in range(len(matrix)) if char in matrix[row]][0]
    char_col = matrix[char_row].index(char)
    return char_row, char_col

def sum_coords(a, b):
    return a[0] + b[0], a[1] + b[1]

def find_path(matrix):
    N, M = len(matrix), len(matrix[0])
    start = find(matrix, 'M')
    end = find(matrix, '*')
    paths = [[start]]
    def get(coord):
        return matrix[coord[0]][coord[1]]
    while paths:
        new_paths = []
        for path in paths:
            for delta in (-1, 0), (1, 0), (0, -1), (0, 1):
                coord = sum_coords(path[-1], delta)
                if (0 <= coord[0] < N and 
                    0 <= coord[1] < M and
                    (len(path) == 1 or coord != path[-2]) and
                    get(coord) != 'X'
                   ):
                   	if coord == end:
                   	    return path + [coord]
                   	else:
                   	    new_paths.append(path + [coord])
        paths = new_paths
    return None

def count_waves(matrix, path):
    N, M = len(matrix), len(matrix[0])
    def get(coord):
        return matrix[coord[0]][coord[1]]
    count = 0
    for (i, path_coord) in enumerate(path[:-1]):
        neighbors = [sum_coords(path_coord, delta) for delta in [(-1, 0), (1, 0), (0, -1), (0, 1)]]
        options = [
			coord for coord in neighbors
        	if (0 <= coord[0] < N and 0 <= coord[1] < M and get(coord) != 'X')
        ]
        if len(options) > (2 if i>0 else 1):
            count += 1
    return count

for _i in range(T):
    # read matrix
    N, M = map(int, input().split())
    matrix = []
    for row in range(N):
        matrix.append(input())
    
    # read expected # waves
    K = int(input())
    
    # find path
    path = find_path(matrix)
    
    # count waves
    count = count_waves(matrix, path)
    
    # print answer
    print('Impressed' if K == count else 'Oops!')


View More Similar Problems

AND xor OR

Given an array of distinct elements. Let and be the smallest and the next smallest element in the interval where . . where , are the bitwise operators , and respectively. Your task is to find the maximum possible value of . Input Format First line contains integer N. Second line contains N integers, representing elements of the array A[] . Output Format Print the value

View Solution →

Waiter

You are a waiter at a party. There is a pile of numbered plates. Create an empty answers array. At each iteration, i, remove each plate from the top of the stack in order. Determine if the number on the plate is evenly divisible ith the prime number. If it is, stack it in pile Bi. Otherwise, stack it in stack Ai. Store the values Bi in from top to bottom in answers. In the next iteration, do the

View Solution →

Queue using Two Stacks

A queue is an abstract data type that maintains the order in which elements were added to it, allowing the oldest elements to be removed from the front and new elements to be added to the rear. This is called a First-In-First-Out (FIFO) data structure because the first element added to the queue (i.e., the one that has been waiting the longest) is always the first one to be removed. A basic que

View Solution →

Castle on the Grid

You are given a square grid with some cells open (.) and some blocked (X). Your playing piece can move along any row or column until it reaches the edge of the grid or a blocked cell. Given a grid, a start and a goal, determine the minmum number of moves to get to the goal. Function Description Complete the minimumMoves function in the editor. minimumMoves has the following parameter(s):

View Solution →

Down to Zero II

You are given Q queries. Each query consists of a single number N. You can perform any of the 2 operations N on in each move: 1: If we take 2 integers a and b where , N = a * b , then we can change N = max( a, b ) 2: Decrease the value of N by 1. Determine the minimum number of moves required to reduce the value of N to 0. Input Format The first line contains the integer Q.

View Solution →

Truck Tour

Suppose there is a circle. There are N petrol pumps on that circle. Petrol pumps are numbered 0 to (N-1) (both inclusive). You have two pieces of information corresponding to each of the petrol pump: (1) the amount of petrol that particular petrol pump will give, and (2) the distance from that petrol pump to the next petrol pump. Initially, you have a tank of infinite capacity carrying no petr

View Solution →