CareerCup

#include "stdafx.h"
#include <stdio.h>
#include <assert.h>


template<class DATA>
class Mtx_3D
{
public:

	Mtx_3D(int x_size, int y_size, int z_size, DATA init, DATA out_of_bounds)
	{
		x_s = x_size;
		y_s = y_size;
		z_s = z_size;
		out_value = out_of_bounds;
		int s = x_s * y_s * z_s;
		data = new DATA[s];

		for (int i = 0; i < s; i++) // fill the array with the value of init
		{
			data[i] = init;
		}
	}//---------------------------------------------------------------------------------------------

	~Mtx_3D()
	{
		delete[] data; // clean up 
	}//---------------------------------------------------------------------------------------------

	DATA get(int x, int y, int z)const
	{
		if (x < 0 || x_s <= x ||
			y < 0 || y_s <= y ||
			z < 0 || z_s <= z)
		{
			return out_value; // we will get the out_of_bounds value if we read out side of the array 
		}

		int a = compute_address(x, y, z);

		return data[a];
	}//---------------------------------------------------------------------------------------------

	void set(int x, int y, int z, DATA d)
	{
		if (x < 0 || x_s <= x ||
			y < 0 || y_s <= y ||
			z < 0 || z_s <= z)
		{
			assert(false);
		}

		int a = compute_address(x, y, z);

		data[a] = d;
	}//---------------------------------------------------------------------------------------------

private:

	int compute_address(int x, int y, int z)const // te the address in one place to keep it consistent  
	{
		return (x * y_s + y) * z_s + z;
	}//---------------------------------------------------------------------------------------------
	
	int x_s, y_s, z_s;
	DATA *data;
	DATA out_value;
};

void dump_plain(int p, Mtx_3D<float> &m, int x, int y)
{
	for (int j = 0; j < y; j++)
	{
		for (int i = 0; i < x; i++)
		{
			printf("%f ", m.get(p, i, j));
		}

		printf("\n");
	}

}



float prob_of_death(int x, int y, int p, int q, int n)
{
	Mtx_3D<float> m(2, p, q, 0.0, 0.0);

	m.set(0, x, y, 1.0); // Put all the probability at the starting position 

	dump_plain(0, m, p, q);
	printf("\n");

	for (int i = 0; i < n; i++) // simulation loop We use a sort of cellular automata system
	{
		for (int x = 0; x < p; x++)
		{
			for (int y = 0; y < q; y++)
			{
				float v = .25 * (
					m.get(i % 2, x + 1, y) + m.get(i % 2, x - 1, y) +
					m.get(i % 2, x, y + 1) + m.get(i % 2, x, y - 1));

				m.set((i + 1) % 2, x, y, v);
			}
		}

		dump_plain((i + 1) % 2, m, p, q);
		printf("\n");
	}

	float sum = 0;

	for (int x = 0; x < p; x++)
	{
		for (int y = 0; y < q; y++)
		{
			sum = sum + m.get(n % 2, x, y);
		}
	}

	return 1 - sum;

}


int _tmain(int argc, _TCHAR* argv[])
{
	float out = prob_of_death(2, 2, 6, 10, 7);
	return 0;
}

The probability has to be split into 3 cases, corners, sides and internal cells. There are 4 corner cells, 2*(P-2) + 2*(Q-2) side cells and (P-2) * (Q-2) internal cells.

The probability to survive in a corner cell is 0.5 since there are 2 edges which will push someone out and 2 edges which will keep them internal.

The probability to survive in a side cell is 0.75 since there is just one edge facing outward and the probability to survive in an internal cell is 1. Given a cell (x,y), the probability to survive in the next move is

(4*0.5 + (2*(p-2) + 2*(q-2)) * 0.75 + (p-2)*(q-2) * 1)/ (p*q), which when solved gets us (pq-0.5q-0.5p)/(pq). Since there are N turns, we need to make it an exponent of N. For N turns, the probability of surviving would be ((pq-0.5q-0.5p)/pq) ^ N

See every position you can reach in n steps. If reaching to a dead end, increase its count. Calculate the probability as (totalSteps-stepsThatLeadToEnd)*100/totalSteps

#include <iostream>
using namespace std;
int tSteps=0;
int total=0;
int d=0;
int P, Q, N;

void Pr(int x, int y, int steps);
int main(){
	int x, y;
	cin>>P>>Q>>N>>x>>y;
	Pr(x, y, 0);
	cout<<(tSteps-d)*100/tSteps<<"%";
	return 0;
}

void Pr(int x, int y, int steps){
	if(steps==N){
		tSteps++;
		if(x<0||x>P){
			d++;
		}
		else if(y<0||y>Q){
			d++;
		}
		return;
	}
	else{
		Pr(x+1, y, steps+1);
		Pr(x-1, y, steps+1);
		Pr(x, y+1, steps+1);
		Pr(x, y-1, steps+1);
	}
}