10592 - Freedom Fighter

[mukit]

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]

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

[andbluer]

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.