Wednesday 18 July 2007

The Castle Guard Problem

Problem Statement
We have a rectangular castle. The first floor is protected by some number of guards. We want to have at least one guard in each row and in each column. You are given a String[] castle. The j-th character of the i-th element of castle is either '.' (free cell) or uppercase 'X' (guard). Return the smallest number of additional guards we have to place in the castle to achieve our goal.

Constraints
- castle will contain between 1 and 50 elements, inclusive.
- Each element of castle will contain between 1 and 50 characters, inclusive.
- All elements of castle will contain the same number of characters.
- Each character of each element of castle will be either '.' or uppercase 'X'.

Examples
0)


{ "....",
"....",
"....",
"...." }

Returns: 4

Here we can place 4 guards on one of the diagonals and that will satisfy us.
1)


{ "XX...",
".XX..",
"...XX" }

Returns: 0

No additional guards needed.
2)


{ "....XXXX",
"........",
"XX.X.XX.",
"........",
"........" }

Returns: 3

3)


{ "........X..",
"...X.......",
"...........",
"..X...X....",
"...........",
"...........",
"........X..",
"...........",
"...........",
"........X..",
".....X....." }

Returns: 6


This code has not yet been tested,
and hence it cannot be guaranteed that this code is a proper solution to the above problem.
Watch the space after some span of time and this will be done.




#include "iostream.h"
#include "conio.h"

char Map[50][50];
int maxE=0, maxC=0;

int scan(int X, int Y, char* dir){
int i=0;
if(dir == "horiz"){
for(i=0;i< maxC;i++){
if(Map[i][Y]=='X')
return 0;
}
return 1;
}
if(dir == "vert"){
for(i=0;i< maxE;i++){
if(Map[X][i]=='X')
return 0;
}
return 1;
}
}

int findShortage(int seedC, int seedE){
static int less=0;
int horiz, vert;
if(seedE > maxE){
return less;
}
horiz = scan(seedC,seedE,"horiz");
vert = scan(seedC,seedE,"vert");
if(horiz && !vert){
findShortage(seedC+1, seedE);
}
if(vert && !horiz){
findShortage(seedC,seedE+1);
}
if(horiz && vert ){
less++;
findShortage(seedC+1, seedC+1);
}
}

void main(void){
clrscr();
int i,j;
cout<<"\nenter maxE: ";cin>>maxE;
cout<<"\nenter maxC: ";cin>>maxC;
for(i=0;i< maxE;i++)
for(j=0;j< maxC;j++){
cout<<"Map["<< i <<"]["<< j <<"]";
cin>>Map[i][j];
}

cout<< findShortage(0,0);
getch();
}

No comments:

Post a Comment