10592 - Freedom Fighter

[windows2k]

Could someone give some tricky inputs or outputs?
"It is granted that a freedom fighter group can fight only one opponent group at a time."
Means that we should calc how many freedom fighter connected to oppoent?
Am I right?

[sohel]

I calculated the number of groups of freedom fighters that are connected to the enemies. Then simply I multiply that amout by 2 to get the total.

I think the judge data does not contain severely technical inputs. And any general approach should get AC.

Try this

................................
.............B.................
........BBBB................
***..***P..................
................................
................................
................................

[windows2k]

I calculated the number of groups of freedom fighters that are connected to the enemies. Then simply I multiply that amout by 2 to get the total.

Yes, I thought my method is the same as yours.

I think the judge data does not contain severely technical inputs. And any general approach should get AC.

Try this

................................
.............B.................
........BBBB................
***..***P..................
................................
................................
................................

The graph should be n*n, the input looks strange.
Have another tricky input/output? Thx

[Ghost77 dimen]

I don't whether tricks exist or not.

But I consider if freedom A and B connect to oppenent C at the same time.

Like this:

BBB
PPP
BBB

I still count that only once.

(Maybe it is the trick. Good Luck)

[windows2k]

BBB
PPP
BBB

My Output:
Sector #1: contain 2 freedom fighter group(s) & 1 enemy group(s)
Total 2 group(s) are in fighting position.
Am I right?

[titid_gede]

it should be 3 groups in fighting position
that is :
- the 1st row 'B'
- 'P'
- the 3rd row 'B'

the B in the 1st row and B in the 3rd row are considered different group.
good luck!

-titid-

[Ghost77 dimen]

Sorry, I find my program have some bugs.

3
BBB
PPP
BBB

3
PPP
BBB
PPP

the last answer of mine are also equal to 4

(I don't know why I still got Accepted, maybe only simple connection will

occur.)

Some other sample

4
BB..
.PP.
B..P
BBBB
Sector #1: contain 1 freedom fighter group(s) & 1 enemy group(s)
Sector #2: contain 1 freedom fighter group(s) & 1 enemy group(s)
Total 4 group(s) are in fighting position.

5
B.B..
.P.P.
.PP.B
BB.P.
B...P
Sector #1: contain 1 freedom fighter group(s) & 0 enemy group(s)
Sector #2: contain 1 freedom fighter group(s) & 0 enemy group(s)
Sector #3: contain 1 freedom fighter group(s) & 1 enemy group(s)
Sector #4: contain 0 freedom fighter group(s) & 1 enemy group(s)
Sector #5: contain 1 freedom fighter group(s) & 0 enemy group(s)
Sector #6: contain 0 freedom fighter group(s) & 1 enemy group(s)
Sector #7: contain 0 freedom fighter group(s) & 1 enemy group(s)
Total 2 group(s) are in fighting position.

Good Luck

[Kamirr]

I check all Yours tests, and i had correct answers. I dont't know what's wrong with my code. Can You look at source, or give more inputs?
Thanks in advance.

[pascal]

type
flist=record
a,b:integer;
end;
var
se,t:array[0..115,0..155]of char;
fft,ent:array[1..2501]of integer;
out:array[1..5221,1..5541]of integer;
fl:array[1..5500]of flist;
spr:array[1..5500]of boolean;
spr2:array[1..5500]of integer;
bb,aa,zz,qq,f,reg,enc,ffc,n,m,bi,bk,z,i,j,d,s,k:longint;
label start;

procedure region(x,y:longint); forward;
procedure freef(x,y,z:longint);forward;
procedure ocup(x,y,z:longint);
begin
t[x,y]:='.';
if (t[x+1,y]='P') then ocup(x+1,y,0);
if (t[x-1,y]='P') then ocup(x-1,y,0);
if (t[x,y+1]='P') then ocup(x,y+1,0);
if (t[x,y-1]='P') then ocup(x,y-1,0);

if (t[x+1,y]='B') then begin inc(ffc); if spr[ffc]=false then
begin spr[ffc]:=true; inc(spr2[enc]);end;freef(x+1,y,1); end;
if (t[x-1,y]='B') then begin inc(ffc); if spr[ffc]=false then
begin spr[ffc]:=true; inc(spr2[enc]);end; freef(x-1,y,1); end;
if (t[x,y+1]='B') then begin inc(ffc); if spr[ffc]=false then
begin spr[ffc]:=true; inc(spr2[enc]);end;freef(x,y+1,1); end;
if (t[x,y-1]='B') then begin inc(ffc); if spr[ffc]=false then
begin spr[ffc]:=true; inc(spr2[enc]);end;freef(x,y-1,1); end;

if (t[x+1,y]='*') then begin inc(aa); fl[aa].a:=x+1; fl[aa].b:=y; end;
if (t[x-1,y]='*') then begin inc(aa); fl[aa].a:=x-1; fl[aa].b:=y; end;
if (t[x,y+1]='*') then begin inc(aa); fl[aa].a:=x; fl[aa].b:=y+1; end;
if (t[x,y-1]='*') then begin inc(aa); fl[aa].a:=x; fl[aa].b:=y-1; end;

end;

procedure freef;
begin
t[x,y]:='.';
if (t[x+1,y]='B') then freef(x+1,y,0);
if (t[x-1,y]='B') then freef(x-1,y,0);
if (t[x,y+1]='B') then freef(x,y+1,0);
if (t[x,y-1]='B') then freef(x,y-1,0);


if (t[x+1,y]='P') then begin inc(enc); if spr[ffc]=false then
begin spr[ffc]:=true;
inc(spr2[enc]); end; ocup(x+1,y,1); end;
if (t[x-1,y]='P') then begin inc(enc); if spr[ffc]=false then
begin spr[ffc]:=true;
inc(spr2[enc]);
end; ocup(x-1,y,1); end;
if (t[x,y+1]='P') then begin inc(enc); if spr[ffc]=false then
begin spr[ffc]:=true;
inc(spr2[enc]);
end; ocup(x,y+1,1); end;
if (t[x,y-1]='P') then begin inc(enc); if spr[ffc]=false then
begin spr[ffc]:=true;
inc(spr2[enc]);
end; ocup(x,y-1,1); end;
if (t[x+1,y]='*') then begin inc(aa); fl[aa].a:=x+1; fl[aa].b:=y; end;
if (t[x-1,y]='*') then begin inc(aa); fl[aa].a:=x-1; fl[aa].b:=y; end;
if (t[x,y+1]='*') then begin inc(aa); fl[aa].a:=x; fl[aa].b:=y+1; end;
if (t[x,y-1]='*') then begin inc(aa); fl[aa].a:=x; fl[aa].b:=y-1; end;

end;

procedure region;
begin
if t[x,y]= 'B' then
begin
inc(ffc);
freef(x,y,0);
end
else if t[x,y]= 'P' then
begin
inc(enc);
ocup(x,y,0);
end
else
begin
t[x,y]:='.';
if t[x+1,y]<>'.' then region(x+1,y);
if t[x-1,y]<>'.' then region(x-1,y);
if t[x,y+1]<>'.' then region(x,y+1);
if t[x,y-1]<>'.' then region(x,y-1);

end;

end;

begin
start:
{}{}{}{}{}{}{}{}{}{ read & clean }{}{}{}{}{}{}
for i:=0 to 51 do
for j:=0 to 51 do
begin
t[i,j]:='.';
se[i,j]:='.';
end;
k:=0;
n:=0;
m:=0;

readln(d);
if d=0 then exit;
for i:=1 to d do
begin
for j:=1 to d do
begin
read(t[i,j]);
end;
readln;
end;
m:=1;
{}{}{}{}{}{}{}{}{}{}{}{}{}{}{ EOF read }{}{}{}{}{}{}{}{}

{}{}{}{}{}{}{}{}{}{}{ seek }{}{}{}{}{}{}{}
for i:=1 to d do
begin
for j:=1 to d do
begin
if (t[i,j]='*')or (t[i,j]='B')or (t[i,j]='P') then
begin
inc(reg);
region(i,j);
for bb:=1 to aa do
begin
if t[fl[bb].a,fl[bb].b]<>'.' then region(fl[bb].a,fl[bb].a);
end;
for qq:=1 to 100 do
begin
if spr2[qq]<>0 then
begin
f:=1+f+spr2[qq];
spr2[qq]:=0;
end;

end;
for qq:=1 to ffc do
begin
spr[qq]:=false;
end;
f:=f+zz;
fft[reg]:=ffc;
ent[reg]:=enc;
ffc:=0;
enc:=0;
aa:=0;
bb:=0;
end;
end;
end;

{}{}{}{}{}{}{}{}{}{}{ EOF seek }{}{}{}{}{}{}{}



{}{}{}{}{}{}{}{}{}{}{ output }{}{}{}{}{}{}{}
for i:=1 to reg do
begin
writeln('Sector #',i,': contain ', fft ,' freedom fighter group(s) & ', ent ,' enemy group(s)');
end;
writeln('Total ', f,' group(s) are in fighting position.');
Writeln('');

reg:=0;
f:=0;

{}{}{}{}{}{}{}{}{}{}{ output }{}{}{}{}{}{}{}

goto start;

end.


[/pascal]

[Mahmud776]

In the judge input data set of this problem, it is clear that there is no such an input set that contain the data of four connected groups. Like..
PPPP
BBBB
PPPP
BBBB
Or,
BBBB
PPPP
BBBB
PPPP
You can consider that highest three groups are connected or in fighting
position.
Here I gave a sample input and output:

Input:
10
......****
.***.*BBBB
PPPP*.BPPP
BBBB*..BBB
PPPP*.***B
******....
B**BB*....
B**BB**..*
***BB**..P
P**BBBB..P

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

I think this will remove all confusions.

Mahmud

[Faisal_Bd]

When I got WA for the first time in this problem, I visited the previous discussions on this one. Some tricky input-output were given there and my solution code was right for them. But I still can't understand what wrong is with my code. I couldn't find out the bug in my code though I tried couple of hours. Anyone can help me please? Or give some other tricky input-output? Here's my code:

Code: Select all

deleted later......

[Raiyan Kamal]

What is your answer for the following cases ?

5
.B...
.....
.....
...P.

1
.

1
B

1
P

2
BP
PB

2
PP
BB

2
BP
BP

3
B.B
.P.
B.B

[Faisal_Bd]

Thanks a lot, Raiyan Kamal. I managed to handle the error and fixed the code and got AC .
The answers for your test cases follow:

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

However, I assumed that a Bangladeshi group can fight against more than one enemy group which is not valid according to the problem description. I think in the input data, there is no test case like this:

PPP
BBB
PPP
In this case, total 2 groups are fighting according to the problem description and my code gives wrong solution(3 groups). However, I shall try to fix it.

Another point, it is stated:

It is granted that a freedom fighter group can fight only one opponent group at a time.

Does it mean that there will not be any case given above? I don't think so.

[Raiyan Kamal]

Dear Faisal,

for the line

It is granted that a freedom fighter group can fight only one opponent group at a time.

I think it means that there will be no such cases where there is a Freedom Fighter group adjacent to more than on enemy groups. But what about enemy groups ? Can they fight more than one Freedom Fighter groups simultaneously ? Its confusing!!

If you assume that a Freedom Fighter group can fight only one Enemy group at a time and vice versa, then there will be no cases like

PPP
BBB
PPP

then you can solve the problem easily ( like you have already done ). But, if that line in the statement bears some special meaning which we have failed to understand, ( i.e. Enemies can fight more than one Freedom Fighter groups simultaneously ) then that code will surely get rejected if they add any case like

BBB
PPP
BBB

and then rejudge it.

Anyways, since a lot of programmers got AC assuming the same, therefore, we can also feel safe to assume this.

[harry]

hi everybody.
can anybody who got a.c. explain his algo.
i got stuck to solve this problem.
plz........

[Raiyan Kamal]

Simple DFS or BFS with a little bit of caution for the special cases. That's all.