1103 - Ancient Messages

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

Moderator: Board moderators

Post Reply
r2ro
New poster
Posts: 38
Joined: Thu Sep 25, 2008 9:26 am

1103 - Ancient Messages

Post by r2ro »

So there is only one user out of the 17 who attempted this problem who failed to get this problem correctly. Sadly, I'm that one user. :oops:

Could anyone please verify the output of the following test cases?

Code: Select all

6 2
00
7c
44
7c
30
00
6 25
0000000000000000000000000
0000000000000000000000000
00001fe0000000000007c0000
00003fe0000000000007c0000
0000000000000000000000000
0000000000000000000000000
10 3
000
778
548
748
578
700
000
7f0
1e0
000
16 2
00
7e
42
7e
42
7e
42
7e
42
7e
42
7e
00
00
4a
00
16 1
0
1
2
3
4
5
6
7
8
9
a
b
c
d
e
f
9 2
00
7e
42
7e
42
7e
42
7e
00
43 2
00
7e
00
7e
42
7e
42
7e
42
7e
00
7e
42
7e
00
7e
42
7e
42
7e
00
7e
42
7e
42
7e
42
7e
42
7e
00
7e
42
7e
42
7e
42
7e
42
7e
42
7e
00
200 50
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
10000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
10000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
10000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
10000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
10000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
10000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
10000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
10000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
10000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
10000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
10000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
10000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
10000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
10000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
10000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
10000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
10000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
10000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
10000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
10000000000000000000000000000000000000000000000000
100 25
0000000000000000000000000
0000000000000000000000000
0000000000000000000000000
0000000000000000000000000
0000000000000000000000000
0000000000000000000000000
0000000000000000000000000
0000000000000000000000000
0000000000000000000000000
00000f8000000000000000000
00001fe000000000000000000
00007ff000000000000000000
00007ff800000000000000000
0000f8f800000000000000000
0001f07c00000000000000000
0001e03c00000000001800000
0001e01c00000000003c00000
0001c01c00000000007c00000
0003c01e0000000000f800000
0003c01e0000000001f000000
0001c01c0000000003f000000
0001c01c0000000007e000000
0001e01c000000000fc000000
0001e03c000000001fc000000
0000e03c000000001fc000000
0000f038000000003ff000000
0000f078000000003ff800000
00007870000000007ff800000
000038f0000000007cfc00000
00003ce0000000007c7c00000
00781fc0f0000000f87c00000
007ffffff0000000f07c00000
007ffffff0000000f07c00000
007ffffff0000001f07c00000
007ffffff0000000e03e00000
007fcf81f0000000603e00000
00000f8000000000003e00000
00000f8000000000003e00000
00000f8000000000003e00000
00000f8000000000001e00000
00000f8000000000001f00000
00000fc000000000001f00000
00000fc000000000001f00000
00000fc000000000001f00000
00000fc000000000000f00000
00001fc000000000000f80000
00001fc000000000000f80000
00001fc000000000000f80000
00001fc000000000000f80000
00001fe000000000000f80000
00001fe000000000000780000
00001fe0000000000007c0000
00001fe0000000000007c0000
00003fe0000000000007c0000
00003fe0000000000007c0000
00003fe0000000000007c0000
00003fe0000c00000003c0000
00000000003ff0000003c0000
00000000007ff8000003e0000
0000000001fffc000003e0000
0000000003e03f000003e0000
0000000007c00f000003e0000
000000000f0003800003f0000
000000000e0001c00003fc000
000000001c0001e00007fe000
000000003c0000e0000fff000
000000073c000070000fdf000
0000001ff8000070001f0f800
0000001ff8000070001e07800
0000003cf0000078001e03800
0000003870000033001e03800
000000307800003fc01e03800
000000703800007fe00e03800
000000703800007ce00e03800
000000703c000078700703800
000000701e0000f0700701000
000000701e0000e0700300000
000000700f0001c0700000000
0000006007800380600000000
000000e003e00700600000000
000000e001fe7e00600000000
000000e000fffc00e00000000
000000e0000ff000e00000000
000000f800038000e00000000
000000fff0000000e00000000
000000fffff00000e00000000
00000003ffffe000c00000000
0000000007ffffc0c00000000
000000000007ffffc00000000
0000000000000fffc00000000
000000000000001fc00000000
0000000000000000000000000
0000000000000000000000000
0000000000000000000000000
0000000000000000000000000
0000000000000000000000000
0000000000000000000000000
0000000000000000000000000
0000000000000000000000000
0000000000000000000000000
150 38
00000000000000000000000000000000000000
00000000000000000000000000000000000000
00000000000000000000000000000000000000
00000000000000000000000000000000000000
00000000000000000000000000000000000000
00000000000000000000000000000000000000
00000000000000000000000000000000000000
00000000000000000000000000000000000000
00000000000000000000000000003000000000
00000f80000000001fff000000007800000000
00001fe0000000007fff80000000ff00000000
00007ff000000000ffffe0000001ff80000000
00007ff800000003fffff0000001fffc000000
0000f8f800000007fffffc000001fffe000000
0001f07c0000000ffffffe000000ffff000000
0001e03c0000001fffffff000000ffff800000
0001e01c0000003fffffff0000007fffc00000
0001c01c0000003fffffff8000007fefc00000
0003c01e0000007fffffffc000003f83c00000
0003c01e000000ffffffffc000001f81e00000
0001c01c000000fffc0fffe000001f01e00000
0001c01c000001fff003ffe000000f01e00000
0001e01c000001ffe001fff000000f00e00000
0001e03c000003ffc0007ff000001e00f00000
0000e03c000003ff80007ff800001e00f00000
0000f038000007ff80003ff800001e00f00000
0000f078000007ff00003ff800001e00f00000
00007870000007ff00001ffc00000e00e00000
000038f000000fff00001ffc00000e00e00000
00003ce000000ffe00000ffc00000e00e00000
00781fc0f0000ffe00000ffc00000f00e00000
007ffffff0000ffc00000ffc00000f01e00000
007ffffff0000ffc00000ffc00000f01e00000
007ffffff0000ffc00000ffc00000701c00000
007ffffff0000ffc00000ffc00000781c00000
007fcf81f0000ffc000007fc00000783c00000
00000f8000000ffc000007fc00000383800000
00000f8000000ffc000007fc000003c7800000
00000f8000000ffc000007fc000001c7800000
00000f8000000ffc000007fc000001e7000000
00000f8000000ffc000007fc000200ef008000
00000fc000000ffc00000ffc0003f8fe3f8000
00000fc000000ffc00000ffc0003ffffff8000
00000fc000000ffc00000ffc0003ffffff8000
00000fc000000ffc00000ffc0003ffffff8000
00001fc000000ffc00000ffc0003ffffff8000
00001fc0000007fe00000ff80003ffffff8000
00001fc0000007fe00000ff80003fffdff8000
00001fc0000007fe00000ff80003c03c000000
00001fe0000007ff00001ff80000007c000000
00001fe0000003ff00001ff00000007c000000
00001fe0000003ff00001ff00000007c000000
00001fe0000001ff80003ff00000007c000000
00003fe0000001ff80003fe00000007c000000
00003fe0000001ff80003fe00000007c000000
00003fe0000000ffc0007fe00000007c000000
00003fe0000000ffc0007fc00000007c000000
000000000000007fe0007fc00000007c000000
000000000000007fe000ff800000007c000000
000000000000007ff001ff800000007c000000
000000000000003ff001ff800000007c000000
000000000000001ff803ff000000007c002000
000000000000001ff803ff000000007c006000
000000000000000ffc07fe000000007c006000
000000000000000ffc0ffc000000007c00c000
000000000000000ffe0ffc000000003e01c000
0000000000000007ff0ff8000000003f03c000
0000000000000003ff1ff0000000003f8f8000
0000000003c00001ffbff00000f0001fff8000
0000000003ffc001ffffe0007ff0000fff8000
0000000003fffff1ffffe3fffff00007ff8000
0000000003fffffffffffffffff00001ff0000
0000000003fffffffffffffffff00000ff0000
0000000003fffffffffffffffff000007f0000
0000000003fffffffffffffffff000001e0000
0000000003fffffffffffffffff000000e0000
0000000003fffffffffffffffff00000020000
0000000003fffffffffffffffff00000000000
0000000003fffffffffffffffff00000000000
0000000003fffffffffffffffff00000000000
0000000003fffffffffffffffff00000000000
0000000003fffffffffffffffff00000000000
0000000003fffffffffffffffff00000000000
0000000003fffffc1ffe0007fff00000000000
0000000003ff80000ffe000000f00000000000
00000000038000000ffe000000000000000000
00000000000000001fff000000000000000000
00000000000000001fff000000000000000000
00000000000000001fff000000000000000000
00000000000000001fff000000000000000000
00000000000000001fff000000000000000000
00000000000000001fff000000000000000000
00000000000000003fff000000000000000000
00000000000000003fff000000000000000000
00000000000000003fff0000000fc000000000
000000000fe000003fff8000003ff000000000
000000003ffc00003fff8000007ffc00000000
00000000fffe00003fff800000fcfc00000000
00000001f01f00003fff800001f03e00000000
00000003e00f80003fff800003e01f00000000
00000003e00780003fff800003e00f00000000
00000003e00780003fff800003c00f00000000
00000003e00f80003fff800003c00f00000000
00000001f00f00007fff800003c00f00000000
00000000f81e00007fffc00003e00f00000000
000000007c3c00007fffc00001e01e00000000
000000003e7800007fffc00000f01e00000000
000000fffffffe007fffc00000f03c00000000
000000fffffffe007fffc00000787800000000
000000fffffffe007fffc000003cf000000000
0000000007c000007fffe000f81fe07c000000
0000000007e000007fffe000fffffffc000000
0000000007e000007fffe000fffffffc000000
000000000fe000007fffe000fffffffc000000
000000000ff00000ffffe000ffc7c0fc000000
000000000ff00000ffffe0000007c000000000
000000001ff00000ffffe000000fc000000000
000000001ff00000ffffe000000fc000000000
000000001ff80000ffffe000000fc000000000
000000001ff80000ffffe000000fc000000000
000000003ff80001ffffe000000fe000000000
000000003ff80001ffffe000000fe000000000
0000000000000001fffff000001fe000000000
0000000000000001fffff000001fe000000000
0000000000000001fffff000001fe000000000
0000000000000001fffff000001ff000000000
0000000000000001fffff000001ff000000000
0000000000000001fffff000001ff000000000
0000000000000001fffff000003ff000000000
0000000000000001fffff000003ff000000000
0000000000000001fffff000003ff000000000
0000000000000001fffff80000000000000000
0000000000000003fffff80000000000000000
0000000000000003fffff80000000000000000
0000000000000003fffff80000000000000000
0000000000000003fffff80000000000000000
0000000000000003fffff80000000000000000
0000000000000003fffff80000000000000000
0000000000000003fffff80000000000000000
0000000000000003fffffc0000000000000000
0000000000000003fffffc0000000000000000
0000000000000007fffffc0000000000000000
0000000000000007fffffc0000000000000000
0000000000000007fffffc0000000000000000
00000000000000000000000000000000000000
00000000000000000000000000000000000000
00000000000000000000000000000000000000
00000000000000000000000000000000000000
00000000000000000000000000000000000000
00000000000000000000000000000000000000
0 0
The output of my WA program.

Code: Select all

Case 1: A
Case 2: WW
Case 3: AKW
Case 4: DWWW
Case 5: AAAKKWWW
Case 6: J
Case 7: ADJKSW
Case 8: WWWWWWWWWWWWWWWWWWWW
Case 9: AKW
Case 10: AAAAA
I'm willing to post my code if it will help.

EDIT: NVM. I found my mistake and got accepted.
Top
gang2k
New poster
Posts: 2
Joined: Tue Jan 20, 2015 10:57 am

Re: 1103 - Ancient Messages

Post by gang2k »

Hi r2ro,
could you share what you have changed to get AC.
I have got WA for a whole day.

I have tried your test cases, and got:

Case 1: A
Case 2: WW
Case 3: KAW
Case 4: DWWW
Case 5: WWWWWWW
Case 6: J
Case 7: WJAKSD
Case 8: WWWWWWW
Case 9: AWK
Case 10: AAAAA

could you tell me the correct answer?
Top
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 1103 - Ancient Messages

Post by brianfry713 »

This will give you AC output:
http://www.udebug.com/UVa/1103
Check input and AC output for thousands of problems on uDebug!
Top
gang2k
New poster
Posts: 2
Joined: Tue Jan 20, 2015 10:57 am

Re: 1103 - Ancient Messages

Post by gang2k »

brianfry713 wrote:This will give you AC output:
http://www.udebug.com/UVa/1103
Thanks, I finially found what was wrong and got AC.
I should read the question more carefully, it said print the codes in alphabetic order!
Top
NAbdulla
New poster
Posts: 31
Joined: Wed Jul 30, 2014 3:40 pm
Contact:
Contact NAbdulla

Re: 1103 - Ancient Messages

Post by NAbdulla »

Can any one help me to find the bug....
my code:

Code: Select all

#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <bitset>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <ios>
#include <set>
#include <map>

using namespace std;

#define PI acos(-1.0)
#define EPS 1e-9
#define INF 1 << 28
#define all(x) (x).begin(), (x).end()
#define pb(x) push_back(x)
#define ppb pop_back
#define mp(a, b) make_pair(a, b)
#define endl '\n'
#define MAX 100000
#define MOD 1000000007
#define setarray(a, b) memset(a, b, sizeof(a))

inline bool isEq(double a, double b){ return (abs(a - b) < EPS); }
inline double NegZero(double x){ if (isEq(x, -0.0))return +0.0; else return x; }

typedef long long ll;
typedef pair<int, int> pii;

#define isValid(a, b) ((a >= 0 && a < b) ? 1 : 0)
int dr[] = { 0, -1, -1, -1, 0, 1, 1, 1 };
int dc[] = { 1, 1, 0, -1, -1, -1, 0, 1 };
char hex2bin[16][5] = { "0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111" };

string grid[205];
int r, c;
void fill2(int nr, int nc, char c1, char c2)//dfs1
{
    if (nr < 0 || nr >= r || nc < 0 || nc >= c || grid[nr][nc] != c1)
        return;
    grid[nr][nc] = c2;
    for (int i = 0; i < 8; i+=2){
        fill2(nr + dr[i], nc + dc[i], c1, c2);
    }
}

int component;
int holes;

void fillBlack(int nr, int nc)//dfs2
{
    if (nr < 0 || nr >= r || nc < 0 || nc >= c)
        return;

    if (grid[nr][nc] == '0'){//a hole in this component
        holes++;
        fill2(nr, nc, '0', 'h');//fill the hole with 'h'
    }
    else if (grid[nr][nc] == '1'){
        grid[nr][nc] = 'b';
        for (int i = 0; i < 8; i+=2){
            fillBlack(nr + dr[i], nc + dc[i]);
        }
    }
    else
        return;
}

int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    //ios_base::sync_with_stdio(false); cin.tie(NULL);

    int holesInComponent[100], cas = 1;
    string inp;
    while (cin >> r >> c){
        if (!r && !c)
            break;

        char ch;
        for (int i = 0; i < r; i++){
            grid[i] = "";
            cin >> inp;
            for (int j = 0; j < c; j++){
                ch = inp[j];
                if (isdigit(ch)){
                    grid[i] += string(hex2bin[ch - '0']);
                }
                else{
                    grid[i] += string(hex2bin[ch - 'a' + 10]);
                }
            }
        }
        c *= 4;
        bool f = 0;
        for(int i = 0; i < r && !f; i++){
            for(int j = 0; j < c; j++){
                if(grid[i][j] == '0'){
                    fill2(i, j, '0', '.');//fill the background with '.'
                    f = 1;
                    break;
                }
            }
        }

        component = 1;
        for (int i = 0; i < r; i++){
            for (int j = 0; j < c; j++){
                if (grid[i][j] == '1'){
                    holes = 0;
                    fillBlack(i, j);
                    holesInComponent[component] = holes;
                    component++;
                }
            }
        }

        string ans;
        for (int i = 1; i < component; i++){
            switch (holesInComponent[i]){
            case 0:
                ans += "W";
                break;
            case 1:
                ans += "A";
                break;
            case 2:
                ans += "K";
                break;
            case 3:
                ans += "J";
                break;
            case 4:
                ans += "S";
                break;
            case 5:
                ans += "D";
                break;
            }
        }
        sort(ans.begin(), ans.end());
        printf("Case %d: %s\n", cas++, ans.c_str());
        /*for (int i = 0; i < r; i++)
            cout << grid[i] << endl;*/
    }
    return 0;
}
Top
touir1
New poster
Posts: 1
Joined: Thu Jul 28, 2016 2:55 am

Re: 1103 - Ancient Messages

Post by touir1 »

Can anyone tell me why i get a wrong answer?
even with the testcases in udebug i get AC and when i submit it tells me WA

Code: Select all

#include <bits/stdc++.h>
#define f first
#define s second

using namespace std;
const int MAX=200;

int n,m;
int M[MAX][MAX];
bool visited[MAX][MAX];
string res;
int color;

int signe[MAX][MAX];

void to_binary(int *M,char hex){
    switch(hex){
        case '0':
            M[0]=0;M[1]=0;M[2]=0;M[3]=0;break;
        case '1':
            M[0]=0;M[1]=0;M[2]=0;M[3]=1;break;
        case '2':
            M[0]=0;M[1]=0;M[2]=1;M[3]=0;break;
        case '3':
            M[0]=0;M[1]=0;M[2]=1;M[3]=1;break;
        case '4':
            M[0]=0;M[1]=1;M[2]=0;M[3]=0;break;
        case '5':
            M[0]=0;M[1]=1;M[2]=0;M[3]=1;break;
        case '6':
            M[0]=0;M[1]=1;M[2]=1;M[3]=0;break;
        case '7':
            M[0]=0;M[1]=1;M[2]=1;M[3]=1;break;
        case '8':
            M[0]=1;M[1]=0;M[2]=0;M[3]=0;break;
        case '9':
            M[0]=1;M[1]=0;M[2]=0;M[3]=1;break;
        case 'a':
            M[0]=1;M[1]=0;M[2]=1;M[3]=0;break;
        case 'b':
            M[0]=1;M[1]=0;M[2]=1;M[3]=1;break;
        case 'c':
            M[0]=1;M[1]=1;M[2]=0;M[3]=0;break;
        case 'd':
            M[0]=1;M[1]=1;M[2]=0;M[3]=1;break;
        case 'e':
            M[0]=1;M[1]=1;M[2]=1;M[3]=0;break;
        case 'f':
            M[0]=1;M[1]=1;M[2]=1;M[3]=1;break;
    }
}

int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int dxw[8]={-1,-1,0,1,1,1,0,-1};
int dyw[8]={0,1,1,1,0,-1,-1,-1};

bool go(int i,int j){
    return (i>=0 && i<n && j>=0 && j<m*4);
}

void bfs(int i,int j){
    color++;
    queue<pair<int,int> > Q;
    pair<int,int> tmp;
    memset(signe,0,sizeof signe);
    Q.push({i,j});
    visited[i][j]=true;
    signe[i][j]=1;
    while(!Q.empty()){
        tmp=Q.front();
        Q.pop();

        M[tmp.f][tmp.s]=color;
        for(int i=0;i<4;i++){
            if(go(tmp.f+dx[i],tmp.s+dy[i]) && !visited[tmp.f+dx[i]][tmp.s+dy[i]] && M[tmp.f+dx[i]][tmp.s+dy[i]]==1){
                Q.push({tmp.f+dx[i],tmp.s+dy[i]});
                visited[tmp.f+dx[i]][tmp.s+dy[i]]=true;
                signe[tmp.f+dx[i]][tmp.s+dy[i]]=1;
            }
        }
    }


    /*cout << endl << "signe:" << endl;
    for(int i=0;i<n;i++){
        for(int j=0;j<m*4;j++){
            cout << signe[i][j];
        }
        cout << endl;
    }*/

    Q=queue<pair<int,int> >();
    int couleur=1;

    for(int i=0;i<n;i++){
        for(int j=0;j<m*4;j++){
            if(signe[i][j]==0){
                couleur++;
                Q.push({i,j});
                signe[i][j]=couleur;
                while(!Q.empty()){
                    tmp=Q.front();
                    Q.pop();
                    for(int k=0;k<4;k++){
                        if(go(tmp.f+dx[k],tmp.s+dy[k]) && signe[tmp.f+dx[k]][tmp.s+dy[k]]==0){
                            Q.push({tmp.f+dx[k],tmp.s+dy[k]});
                            signe[tmp.f+dx[k]][tmp.s+dy[k]]=couleur;
                        }
                    }
                }
            }
        }
    }

    /*cout << endl << "colored:" << endl;
    for(int i=0;i<n;i++){
        for(int j=0;j<m*4;j++){
            cout << signe[i][j];
        }
        cout << endl;
    }*/

    // 1 white = W
    // 2 whites = A
    // 3 whites = K
    // 4 whites = J
    // 5 whites = S
    // 6 whites = D
    switch(couleur-1){
        case 1: res=res+'W';break;
        case 2: res=res+'A';break;
        case 3: res=res+'K';break;
        case 4: res=res+'J';break;
        case 5: res=res+'S';break;
        case 6: res=res+'D';break;
    }
    /*
    cout << "end bfs: " << res[res.length()-1] << endl;
    */
}

int main()
{
    //ofstream output("output.out");
    string tmp;
    int cc;
    int Case_t=1;
    while(true){
        cin >> n;
        cin >> m;
        if(n==0 && m==0)
            break;
        //cout << "coord: " << n << " " << m << endl;
        memset(M,0,sizeof M);
        memset(signe,0,sizeof signe);
        memset(visited,false,sizeof visited);
        color=1;

        for(int i=0;i<n;i++){
            cin >> tmp;
            cc=0;
            for(int j=0;j<tmp.length();j++){
                to_binary(M[i]+cc*4,tmp[j]);
                cc++;
            }
        }
        /*cout << endl << "matrix:" << endl;
        for(int i=0;i<n;i++){
            for(int j=0;j<m*4;j++){
                cout << M[i][j];
            }
            cout << endl;
        }*/
        //int test=1;
        res="";
        for(int i=0;i<n;i++){
            for(int j=0;j<m*4;j++){
                if(M[i][j]==1){
                    //cout << "bfs: " << test++ << endl;
                    bfs(i,j);
                }
            }
        }
        sort(res.begin(),res.end());
        //output << "Case " << Case_t << ": " << res << endl;
        cout << "Case " << Case_t++ << ": " << res << endl;
    }
    return 0;
}
Top
Post Reply

Return to “Volume 11 (1100-1199)”