10592 - Freedom Fighter

All about problems in Volume 105. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

mukit
New poster
Posts: 48
Joined: Wed Nov 21, 2007 10:09 am
Location: Dhaka , Bangladesh
Contact:

Re: 10592 - Freedom Fighter

Post by mukit » Tue Sep 09, 2008 12:03 pm

Hi, I'm getting wrong answer in this problem.
I checked all the given input-output.

Please help

Code: Select all

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
//enum{noCol=-1,white,red,green,pink,blue,gray,black};

#define noCol -1
#define white 0
#define red 1
#define green 2
#define pink 3
#define blue 4
#define gray 5
#define black 6
#define gold 7
#define silver 8

int sector,fg,eg,pos;
int m[60][60];
int m1[60][60];
void color(int i,int j,int c1,int c2)
{
	if(m[i][j+1]==c1)
	{
		m[i][j+1]=c2;
		color(i,j+1,c1,c2);
	}
	if(m[i+1][j]==c1)
	{
		m[i+1][j]=c2;
		color(i+1,j,c1,c2);
	}
	if(m[i][j-1]==c1)
	{
		m[i][j-1]=c2;
		color(i,j-1,c1,c2);
	}
	if(m[i-1][j]==c1)
	{
		m[i-1][j]=c2;
		color(i-1,j,c1,c2);
	}
}
void backtrack(int i,int j)
{
	if(m[i][j]==white || m[i][j]==gold)
	{
		m[i][j]=noCol;
	}
	else if(m[i][j]==red)
	{
		fg++;
		m[i][j]=gold;
		color(i,j,red,gold);
	}
	else if(m[i][j]==green)
	{
		eg++;
		m[i][j]=gold;
		color(i,j,green,gold);
	}
	if(m[i][j+1]==white || m[i][j+1]==green || m[i][j+1]==red || m[i][j+1]==gold)
	{
		backtrack(i,j+1);
	}
	if(m[i+1][j]==white || m[i+1][j]==green || m[i+1][j]==red || m[i+1][j]==gold)
	{
		backtrack(i+1,j);
	}
	if(m[i][j-1]==white || m[i][j-1]==green || m[i][j-1]==red || m[i][j-1]==gold)
	{
		backtrack(i,j-1);
	}
	if(m[i-1][j]==white || m[i-1][j]==green || m[i-1][j]==red || m[i-1][j]==gold)
	{
		backtrack(i-1,j);
	}
}
void find_total(int i,int j)
{
	if(m[i][j+1]==red)
	{
		if(m[i][j]==green)
		{
			pos+=2;
		}
		else if(m[i][j]==black)
		{
			pos++;
		}
		m[i][j+1]=gray;
		m[i][j]=black;
		color(i,j+1,red,gray);
		color(i,j+1,green,black);
	}
	if(m[i+1][j]==red)
	{
		if(m[i][j]==green)
		{
			pos+=2;
		}
		else if(m[i][j]==black)
		{
			pos++;
		}
		m[i+1][j]=gray;
		m[i][j]=black;
		color(i+1,j,red,gray);
		color(i,j+1,green,black);
	}
	if(m[i][j-1]==red)
	{
		if(m[i][j]==green)
		{
			pos+=2;
		}
		else if(m[i][j]==black)
		{
			pos++;
		}
		m[i][j-1]=gray;
		m[i][j]=black;
		color(i,j-1,red,gray);
		color(i,j+1,green,black);
	}
	if(m[i-1][j]==red)
	{
		if(m[i][j]==green)
		{
			pos+=2;
		}
		else if(m[i][j]==black)
		{
			pos++;
		}
		m[i-1][j]=gray;
		m[i][j]=black;
		color(i-1,j,red,gray);
		color(i,j+1,green,black);
	}
}
int main()
{
	int n;
	char ch;
	while(cin>>n)
	{
		memset(m,noCol,sizeof(m));
		memset(m1,noCol,sizeof(m1));
		sector=0;
		fg=0;
		eg=0;
		pos=0;
		if(n==0)
		{
			break;
		}
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<n;j++)
			{
				cin>>ch;
				if(ch=='.')
				{
					m[i+1][j+1]=m1[i+1][j+1]=noCol;
				}
				if(ch=='*')
				{
					m[i+1][j+1]=m1[i+1][j+1]=white;
				}
				else if(ch=='B')
				{
					m[i+1][j+1]=m1[i+1][j+1]=red;
				}
				else if(ch=='P')
				{
					m[i+1][j+1]=m1[i+1][j+1]=green;
				}
			}
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				if(m[i][j]==white || m[i][j]==red || m[i][j]==green)
				{
					sector++;
					backtrack(i,j);
					printf("Sector #%d: contain %d freedom fighter group(s) & %d enemy group(s)\n",sector,fg,eg);
					fg=0;
					eg=0;
				}
			}
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				m[i][j]=m1[i][j];
			}
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				if(m1[i][j]==green)
				{
					m1[i][j]=noCol;
					find_total(i,j);
				}
			}
		}
		if(sector>0)
		{
			printf("Total %d group(s) are in fighting position.\n",pos);
		}
		printf("\n");
	}
	return 0;
}


Thanks in advance to all.

Articuno
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm
Location: IUT-OIC, Dhaka, Bangladesh

Re: 10592 - Freedom Fighter

Post by Articuno » Fri Oct 30, 2009 6:49 am

I don't understand one thing. In the problem description it is said that
It is granted that a freedom fighter group can fight only one opponent group at a time.
So why there are inputs like these in the previous posts?? Can anyone tell me?

Code: Select all

10
......****
.***.*BBBB
PPPP*.BPPP
BBBB*..BBB
PPPP*.***B
******....
B**BB*....
B**BB**..*
***BB**..P
P**BBBB..P
I got AC without considering this type of test cases.........
May be tomorrow is a better day............ :)

andbluer
New poster
Posts: 1
Joined: Thu Feb 20, 2014 12:48 pm

Re: 10592 - Freedom Fighter

Post by andbluer » Tue Feb 25, 2014 6:53 pm

Here is another test case:

Code: Select all

7
*******
*BBBBB*
*B***B*
*B*P*B*
*B***B*
*BBBBB*
*******
0
The corect answer is:

Code: Select all

Sector #1: contain 1 freedom fighter group(s) & 1 enemy group(s)
Total 0 group(s) are in fighting position.


Also, one group can only be adjacent to at most one other group. So, most of the test cases given previously are invalid.

Post Reply

Return to “Volume 105 (10500-10599)”