Coin Game: Strategy

general
, , ,
1

I have an interesting problem via some other programming platform but I could not get its solution. What should be the strategy for this question.(Note: It does not comes from any running programming competition. It is just a practice problem can be found here). Here Goes the problem.

You have a rectangular board consisting of n rows, numbered from 1 to n and m columns, numbered from 1 to m. The top left is (1,1) and bottom right is (n,m). Initially - at time 0 - there is a coin on the top-left cell of your board. Each cell of your board contains one of these letters:

*, exactly one of your cells has letter ‘*’.

U, If at time t, the coin is on the cell(i,j) and cell(i,j) has letter ‘U’, the coin will be on the cell(i-1,j) in time t+1 if i > 1. otherwise there is no coin on your board at time t+1.

L, If at time t, the coin is on the cell(i,j) and cell(i,j) has letter ‘L’, the coin will be on the cell(i,j-1) in time t+1 if j > 1. otherwise there is no coin on your board at time t+1.

D, If at time t, the coin is on the cell(i,j) and cell(i,j) has letter ‘D’, the coin will be on the cell(i+1,j) in time t+1 if i < n. otherwise there is no coin on your board at time t+1.

R, If at time t, the coin is on the cell(i,j) and cell(i,j) has letter ‘R’, the coin will be on the cell(i,j+1) in time t+1 if j < m. otherwise there is no coin on your board at time t+1.

When the coin reaches the cell that has letter ‘’ it will be there permanently. When you punch on your board, your timer starts and the coin moves between cells. before doing that you want to do some operation so that you could be sure that at time k the coin will be on the cell having letter ‘’. In each operation you can select a cell with some letter other than ‘*’ and change the letter to ‘U’, ‘L’, ‘R’ or ‘D’. You want to do as few operations as possible in order to achieve your goal. Your task is to find the minimum number of operations.

Input:

The first line of input contains three integers n and m and k.

Next n lines contains m letters which describe you board.

n and m are integers less than 51.

k is less than 1001.

Output:

on the only line of the output print an integer being the answer to the test.

If you cannot achieve your goal, output -1 please.

Sample input :

2 2 3

RD

*L

Sample output :

0

Sample input :

2 2 1

RD

*L

Sample output :

1

Explanation :

In the first example you don’t have to change any letters, but in the second example you should change the letter of cell (1,1) to ‘D’.

2

Any Help will be appreciated with Karma.!! :slight_smile:

3

You already know that this problem can be solved using Dynamic Programming. Here is a code which solves the problem. If you find any difficulty, feel free to ask.

#include <algorithm>
#include <iostream>
#include <string>

using namespace std;

#define MAXN 50
#define MAXM 50
#define INF 1000000

int N, M, K, ti, tj;
string board[MAXN];
int p[MAXN][MAXM];

void dfs(int i, int j, int k, int c) {
    if (i >= 0 && j >= 0 && i < N && j < M && c < p[i][j] && k <= K) {
        p[i][j] = c;

        dfs(i - 1, j, k + 1, c + !(board[i][j] == 'U'));
        dfs(i, j - 1, k + 1, c + !(board[i][j] == 'L'));
        dfs(i + 1, j, k + 1, c + !(board[i][j] == 'D'));
        dfs(i, j + 1, k + 1, c + !(board[i][j] == 'R'));
    }
}

int getMinOperations() {
    for (int i = 0; i < MAXN; i++)
        for (int j = 0; j < MAXM; j++)
            p[i][j] = INF;

    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            if (board[i][j] == '*') {
                ti = i;
                tj = j;
            }

    dfs(0, 0, 0, 0);

    return (p[ti][tj] == INF ? -1 : p[ti][tj]);
}

int main() {
    cin >> N >> M >> K;

    for (int i = 0; i < N; i++)
        cin >> board[i];

    cout << getMinOperations() << endl;

    return 0;
}
2 Likes
4

v ryt answer…!! thanks @bugkiller you are really a bug killer… I am posting my original code as answer.

1 Like
5

My original code was like this…!!

'#include<iostream>

using namespace std;  
int n,k,m;  
int checkAv(char** grid)  
{  
	int i,j;
  	for(i=0;i<n;i++)
  	{
  		for(j=0;j<m;j++)
  		{
  			if(grid[i][j]=='*')
  			{
  				
  				if(i+j>k)
  				{
  					return -1;
  				}
  			}
  		}
  	}
  	return 0;
}  
//dir
//
//1	UP
//2	DOWN
//4	RIGHT
//8	LEFT
    
 int countW(char **grid,int i,int j,int t,int dir,int ans)
  {
  	int a1=10000,a2=10000,a3=10000,a4=10000;
  	cout<<" i "<<i<<" j "<<j<<" t "<<t<<" ans "<<ans<<endl;  
  	cout<<" dir&1 "<<(dir&1)<<" dir&2 "<<(dir&2)<<" dir&4 "<<(dir&4)<<" dir&8 "<<(dir&8)<<endl;
  	
  	if(grid[i][j]=='*')
  	{
  		return ans;
      }
  	if(t==k&&grid[i][j]!='*')
  		return 10000;
  	
  	if(grid[i][j]=='U')
  	{
  		if(i>0&&((dir&1)==0))//U
  		{
  			a1=countW(grid,i-1,j,t+1,1,ans);
  	    }
  		if(i<n-1&&((dir&2)==0))//D
  		{
  			a2=countW(grid,i+1,j,t+1,2,ans+1);
  		}
  		if(j>0&&((dir&8)==0))  //L
  		{
  			a3=countW(grid,i,j-1,t+1,8,ans+1);
  		}
  		if(j<m-1&&((dir&4)==0))   //R
  		{
  			a4=countW(grid,i,j+1,t+1,4,ans+1);		
  	    }
  	
  	
  	}
  	else if(grid[i][j]=='D')
  	{
  		if(i>0&&((dir&1)==0))//U
  		{
 			a1=countW(grid,i-1,j,t+1,1,ans+1);
  		}
  		if(i<n-1&&((dir&2)==0))//D
  		{
  			a2=countW(grid,i+1,j,t+1,2,ans);
  		}
  		if(j>0&&((dir&8)==0))  //L
  		{
  			a3=countW(grid,i,j-1,t+1,8,ans+1);
  		}
  		if(j<m-1&&((dir&4)==0))   //R
  		{
  			a4=countW(grid,i,j+1,t+1,4,ans+1);		
  	    } 
  	
  	}
  	else
  	if(grid[i][j]=='L')
  	{
  		if(i>0&&((dir&1)==0))//U
  		{
  			a1=countW(grid,i-1,j,t+1,1,ans+1);
  		}
  		if(i<n-1&&((dir&2)==0))//D
  		{
  			a2=countW(grid,i+1,j,t+1,2,ans+1);
  		}
  		if(j>0&&((dir&8)==0))  //L
  		{
  			a3=countW(grid,i,j-1,t+1,8,ans);
  		}if(j<m-1&&((dir&4)==0))   //R
  		{
  			a4=countW(grid,i,j+1,t+1,4,ans+1);		
  	    }
  	
  	}
  	else if(grid[i][j]=='R')
  	{
  		if(i>0&&((dir&1)==0))
  		{
  			a1=countW(grid,i-1,j,t+1,1,ans+1);
  		}
  		if(i<n-1&&((dir&2)==0))//D
  		{
  			a2=countW(grid,i+1,j,t+1,2,ans+1);
  		}
  		if(j>0&&((dir&8)==0))  //L
  		{
  			a3=countW(grid,i,j-1,t+1,8,ans+1);
  		}
  		if(j<m-1&&((dir&4)==0))   //R
  		{
  			a4=countW(grid,i,j+1,t+1,4,ans);		
  	    }
  	
  	}
  	cout<<a1<<" "<<a2<<" "<<a3<<" "<<a4<<endl;
   	int small=10000;
  	if(a1<small)
  		small=a1;
  	if(a2<small)
  		small=a2;
  	if(a3<small)
  		small=a3;
  	if(a4<small)
  		small=a4;
  	return small;
}  
  int countW2(char **grid,int i,int j,int t,int dir,int ans)
  {
  	
  }     
int main()
  {
  	cin>>n>>m>>k;
  	char **grid;
  	grid=new char*[n];
  	for(int i=0;i<n;i++)
  		grid[i]=new char[m+1];
  	for(int i=0;i<n;i++)
  	{
  			cin>>grid[i];
  	}
  	int res;
  	res=checkAv(grid);
  	if(res==-1)
  	{
  		cout<<res<<endl;
  	}
  	else
  	{
  		res=countW(grid,0,0,0,0,0);	
  		if(res!=10000)
  			cout<<res<<endl;
  		else
  			cout<<-1<<endl;
  	}
  	return 0;
  }

Can We discuss what were the problems in this approach apart from the fact that it doesn’t uses DP.

6

hopefull for getting an answer soon :slight_smile: