Page 1 of 1

10274 - Fans and Gems

Posted: Wed Jan 28, 2004 7:58 pm
by Whinii F.
Hi! I'm solving this problem and confused about the sample input and output.

For the sample input given below,

Code: Select all

########
##   1##
##  2  #
#  1  ##
##2   ##
#   1@##
###   ##
#### ###
########
They have LURD (left, up, right, down) as the desired output. Two 2 s collide after LU and three 1 s disappear after RD.

but why DRU is not a valid output? Following is a simulation on DRU.

Code: Select all

########
##   1##
##  2  #
#  1  ##
##2   ##
#   1@##
###   ##
#### ###
########

After D
########
##    ##
##     #
#     ##
##    ##
# 2  1##
###12@##
####1###
########

After R: two 2 s disappear
########
##    ##
##     #
#     ##
##    ##
#    1##
###1 @##
####1###
########

After U: so we can remove all gems
########
## 111##
##   @ #
#     ##
##    ##
#     ##
###   ##
#### ###
########

I'm whole puzzled. Thanks in advance! :wink:

Regards,

Posted: Wed Jan 28, 2004 10:08 pm
by Adrian Kuegel
After the two 2 disapper, the 1 moves one right (because the fans are still blowing). The fans stop blowing if nothing changes.
By the way, because the 1 moves one right, it will disappear together with the 1 below, so only one 1 is left and you can't find a solution any more

Posted: Sat Jan 31, 2004 10:38 am
by Observer
Juz wanna ask, could we solve this problem with backtracking + B&B? Or is BFS the only way? (heard from a friend of mine)

Posted: Fri Feb 06, 2004 2:13 pm
by Whinii F.
Adrian: Yes, very true! I forgot to implement "keep blowing wind till there's no chages" feature. Now my program solves the example case correctly. Thanks!

Observer: It seems BFS is feasible (However it is a bit tricky to create lexicographically smallest output) . I used BFS and it runs fast.. (< 0.5sec) but painfully, I get WA. So what I'm saying, may be whole wrong. :wink:

Posted: Thu Feb 12, 2004 12:04 pm
by Observer
I don't know hashing, so I just used DFS in my code.... And guess what, I got ACC in 0.5 sec!! :D

This is indeed a great problem~ and my solution looks long and ugly :wink:

10274 - Fans and Gems (Need I/O verification)

Posted: Sun Feb 20, 2005 6:22 pm
by txandi
Can anybody check this I/O??? I keep getting WA and I don't know why.

Code: Select all

20
5 14
##############
#@   1 3   1@#
#@#2#     #  #
#213  @13  @3#
##############

9 9
#########
#     3 #
# 3  @  #
#21  1@ #
#3     3#
# 2  # @#
#   #   #
## 3 2  #
#########

11 13
#############
# 2   2@ #  #
#2 3@ 1 @@ 2#
# 2    @2   #
#3 2 @ #  3 #
##    2#   2#
#3        1 #
##   #    3 #
#  #   1@# 1#
# 3#2  31 @##
#############

5 12
############
#3 @@ 2 1 3#
# 3 1#@ #  #
#      # 2 #
############

12 9
#########
#  12 #2#
#  #   1#
#      3#
#    2#1#
#1312#  #
# 2#    #
#      2#
###   1 #
#     23#
#@    @ #
#########

7 20
####################
#  ##     3#  1 23##
#3  @ 3 3          #
#1 3  1 #2  2    2 #
##   #      #1  1  #
# 2  #13@        21#
####################

11 7
#######
##   @#
# 2  @#
#  3#@#
#2# # #
# 3  2#
#    ##
# 3  ##
#3@  ##
# # 2 #
#######

7 15
###############
#  1 12     # #
#3  #23231 3  #
# 2 #     # 2 #
#   #  123 3 1#
# 2# 1  @1##23#
###############

5 9
#########
#  @1   #
#   3  ##
#1   31 #
#########

9 9
#########
# 1   1 #
#1   ####
# 2#  3 #
#  2   ##
#3    1 #
# 1     #
#  1@@  #
#########

10 7
#######
#1 1  #
#   @ #
##  1 #
#     #
#3#  ##
# # #1#
#   ###
#  1 3#
#######

7 11
###########
#    1#32##
#     2  3#
#@ @3   # #
#       2 #
#2  3   31#
###########

9 14
##############
#     2 12   #
# @          #
#1   #13 1@  #
#  #      #  #
#2# #   2 3  #
##  3 2   @@##
# 1        21#
##############

8 18
##################
####  # ##      3#
#21 #   1 @@  @ ##
#3     @# 2  2 23#
#  #1@ #      # 1#
# 2             3#
#3  @    #       #
##################

12 20
####################
#       2# # 2  1 3#
#1  @1      3 #    #
#@2@1#@   @3#2#  2 #
#   #  2           #
#3#1       @1      #
#  2 #     @  13   #
# 2    1##2@#   #23#
#21   # 13    2   ##
#  @      #       ##
# # 1@    #@ 231   #
####################

11 7
#######
###1@2#
# 1 3 #
# #   #
#  3@ #
#     #
#23# @#
#32   #
#2    #
#  32 #
#######

5 13
#############
#  # 21  @ 3#
##1#@ #  2 2#
#   3    1  #
#############

7 19
###################
#3  1#3 1  3  @#1 #
#2#  @@   @323 1# #
#  3     @  #     #
#  ##23   1#12  21#
# 1#       2#     #
###################

9 12
############
#3#23 2  ###
# 31   @  ##
#3  2#3 #3 #
#    2  3 @#
# 1   1  ###
#      2 2 #
# 1  #13  @#
############

9 17
#################
# 3 3  212 3 #32#
# 1    2  3 @  ##
#  1        1 1 #
##2 2##1  1#    #
#   @ 2 3   #3  #
#2  1   13      #
#@3  3 3 @ @ 3#@#
#################

My program gives

Code: Select all

RDLULRD
DRURDLDLURU
RLURULURDL
-1
RDLULURDLDRD
RDLDLURDRURD
LDRD
-1
-1
RDLDR
-1
LDRDLUL
RULDRDLDRUL
RDRULURDLD
RDLULRUL
DLUD
-1
LULDLURDRD
DLDRU
DURULDRU
If this I/O is correct, can anybody tell me some critical one?

Thanks!!

Posted: Mon Feb 28, 2005 10:26 pm
by txandi
I got AC now. The input above this is ok.
My (silly) mistake:
There is one line after each map, ignore them.
I assumed this line was empty, but I was wrong, it was full of garbage... I shoud have thought about this before wasting a lot of time debugging a correct program... In my opinion these kind of "tricky" inputs shoud be supressed from the judge.
Anyway it's AC now, I'm happy :D

10274 Fans and Gems

Posted: Sun Apr 23, 2006 1:52 pm
by LlatzerandToni
Hi!

We have a problem. Our output isn't correct for the online-judge. However, the answer seems correct. We don't know if it is just a problem of output writing. We have tried this input:
26
9 8
########
##...1##
##..2..#
#..1..##
##2...##
#...1@##
###...##
####.###
########

7 8
########
#212121#
#......#
#.#.#.##
#.#....#
#.....##
########
jdsnjcdsjasnbcanxbsxbcajhsxdb
4 4
####
#1.#
#@2#
####

5 5
#####
#1..#
##@@#
#1..#
#####

5 14
##############
#@...1.3...1@#
#@#2#.....#..#
#213..@13..@3#
##############
djsnfcjdsnjfsnjnsjn32j32j32j4n32jkn4jn2jn4kj32n432.4nj324n2jn42.32n432jn4324j2.432.42j3.4324j24j2.4j324j.4j32.4j32.4j32.4j242432j.4j2.4j32.4j32.4j2.4j32n4j32
9 9
#########
#.....3.#
#.3..@..#
#21..1@.#
#3.....3#
#.2..#.@#
#...#...#
##.3.2..#
#########

11 13
#############
#.2...2@.#..#
#2.3@.1.@@.2#
#.2....@2...#
#3.2.@.#..3.#
##....2#...2#
#3........1.#
##...#....3.#
#..#...1@#.1#
#.3#2..31.@##
#############

5 12
############
#3.@@.2.1.3#
#.3.1#@.#..#
#......#.2.#
############

12 9
#########
#..12.#2#
#..#...1#
#......3#
#....2#1#
#1312#..#
#.2#....#
#......2#
###...1.#
#.....23#
#@....@.#
#########

7 20
####################
#..##.....3#..1.23##
#3..@.3.3..........#
#1.3..1.#2..2....2.#
##...#......#1..1..#
#.2..#13@........21#
####################

11 7
#######
##...@#
#.2..@#
#..3#@#
#2#.#.#
#.3..2#
#....##
#.3..##
#3@..##
#.#.2.#
#######

7 15
###############
#..1.12.....#.#
#3..#23231.3..#
#.2.#.....#.2.#
#...#..123.3.1#
#.2#.1..@1##23#
###############

5 9
#########
#..@1...#
#...3..##
#1...31.#
#########

9 9
#########
#.1...1.#
#1...####
#.2#..3.#
#..2...##
#3....1.#
#.1.....#
#..1@@..#
#########

10 7
#######
#1.1..#
#...@.#
##..1.#
#.....#
#3#..##
#.#.#1#
#...###
#..1.3#
#######

7 11
###########
#....1#32##
#.....2..3#
#@.@3...#.#
#.......2.#
#2..3...31#
###########

9 14
##############
#.....2.12...#
#.@..........#
#1...#13.1@..#
#..#......#..#
#2#.#...2.3..#
##..3.2...@@##
#.1........21#
##############

8 18
##################
####..#.##......3#
#21.#...1.@@..@.##
#3.....@#.2..2.23#
#..#1@.#......#.1#
#.2.............3#
#3..@....#.......#
##################

12 20
####################
#.......2#.#.2..1.3#
#1..@1......3.#....#
#@2@1#@...@3#2#..2.#
#...#..2...........#
#3#1.......@1......#
#..2.#.....@..13...#
#.2....1##2@#...#23#
#21...#.13....2...##
#..@......#.......##
#.#.1@....#@.231...#
####################
.
11 7
#######
###1@2#
#.1.3.#
#.#...#
#..3@.#
#.....#
#23#.@#
#32...#
#2....#
#..32.#
#######
.
5 13
#############
#..#.21..@.3#
##1#@.#..2.2#
#...3....1..#
#############

7 19
###################
#3..1#3.1..3..@#1.#
#2#..@@...@323.1#.#
#..3.....@..#.....#
#..##23...1#12..21#
#.1#.......2#.....#
###################
.
9 12
############
#3#23.2..###
#.31...@..##
#3..2#3.#3.#
#....2..3.@#
#.1...1..###
#......2.2.#
#.1..#13..@#
############
.
9 17
#################
#.3.3..212.3.#32#
#.1....2..3.@..##
#..1........1.1.#
##2.2##1..1#....#
#...@.2.3...#3..#
#2..1...13......#
#@3..3.3.@.@.3#@#
#################

12 20
####################
#@@1232#3123123....#
#.....##....#......#
#1.#....#..........#
#.2......#.#.......#
#..3#..............#
#3..333.3.3.3.3....#
#@..#..@..3.3@.....#
#....#.##..........#
#.1.2.1..2.1#2.1.21#
#.3.3.3.3.3#3.3..13#
####################
vndsfjfndjnvfjdnvjv .dnfjvfdjnvfjdngjdffg.df.j4..3j32h432h4.3h32h4.j32hj32hj32.h4j32h
3 6
######
#1##1#
######
And got this output:
LURD
DL
-1
DRDLURD
RDLULRD
DRURDLDLURU
RLURULURDL
-1
RDLULURDLDRD
RDLDLURDRURD
LDRD
-1
-1
RDLDR
-1
LDRDLUL
RULDRDLDRUL
RDRULURDLD
RDLULRUL
DLUD
-1
ULURULDRDLRDLUL
DLDRU
RLUDRU
DLULULDRDRDL
-1
We don't exactly know wether we must put an endline at the last answer. We have tried both options with no results because we always get WA.
If anyone knows which could be our problem...it would be reallly great.
Thanks, have a nice problemsetday!!!!!!!!

PS:We have dots instead of spaces in our input but it was just to put this entry here in the forum(dont be lazy and get a replace in any editor to try the input).

Re: 10274 - Fans and Gems

Posted: Tue May 01, 2012 10:53 pm
by brianfry713
For your input:

Code: Select all

26
9 8
########
##   1##
##  2  #
#  1  ##
##2   ##
#   1@##
###   ##
#### ###
########

7 8
########
#212121#
#      #
# # # ##
# #    #
#     ##
########
jdsnjcdsjasnbcanxbsxbcajhsxdb
4 4
####
#1 #
#@2#
####

5 5
#####
#1  #
##@@#
#1  #
#####

5 14
##############
#@   1 3   1@#
#@#2#     #  #
#213  @13  @3#
##############
djsnfcjdsnjfsnjnsjn32j32j32j4n32jkn4jn2jn4kj32n432 4nj324n2jn42 32n432jn4324j2 432 42j3 4324j24j2 4j324j 4j32 4j32 4j32 4j242432j 4j2 4j32 4j32 4j2 4j32n4j32
9 9
#########
#     3 #
# 3  @  #
#21  1@ #
#3     3#
# 2  # @#
#   #   #
## 3 2  #
#########

11 13
#############
# 2   2@ #  #
#2 3@ 1 @@ 2#
# 2    @2   #
#3 2 @ #  3 #
##    2#   2#
#3        1 #
##   #    3 #
#  #   1@# 1#
# 3#2  31 @##
#############

5 12
############
#3 @@ 2 1 3#
# 3 1#@ #  #
#      # 2 #
############

12 9
#########
#  12 #2#
#  #   1#
#      3#
#    2#1#
#1312#  #
# 2#    #
#      2#
###   1 #
#     23#
#@    @ #
#########

7 20
####################
#  ##     3#  1 23##
#3  @ 3 3          #
#1 3  1 #2  2    2 #
##   #      #1  1  #
# 2  #13@        21#
####################

11 7
#######
##   @#
# 2  @#
#  3#@#
#2# # #
# 3  2#
#    ##
# 3  ##
#3@  ##
# # 2 #
#######

7 15
###############
#  1 12     # #
#3  #23231 3  #
# 2 #     # 2 #
#   #  123 3 1#
# 2# 1  @1##23#
###############

5 9
#########
#  @1   #
#   3  ##
#1   31 #
#########

9 9
#########
# 1   1 #
#1   ####
# 2#  3 #
#  2   ##
#3    1 #
# 1     #
#  1@@  #
#########

10 7
#######
#1 1  #
#   @ #
##  1 #
#     #
#3#  ##
# # #1#
#   ###
#  1 3#
#######

7 11
###########
#    1#32##
#     2  3#
#@ @3   # #
#       2 #
#2  3   31#
###########

9 14
##############
#     2 12   #
# @          #
#1   #13 1@  #
#  #      #  #
#2# #   2 3  #
##  3 2   @@##
# 1        21#
##############

8 18
##################
####  # ##      3#
#21 #   1 @@  @ ##
#3     @# 2  2 23#
#  #1@ #      # 1#
# 2             3#
#3  @    #       #
##################

12 20
####################
#       2# # 2  1 3#
#1  @1      3 #    #
#@2@1#@   @3#2#  2 #
#   #  2           #
#3#1       @1      #
#  2 #     @  13   #
# 2    1##2@#   #23#
#21   # 13    2   ##
#  @      #       ##
# # 1@    #@ 231   #
####################
 
11 7
#######
###1@2#
# 1 3 #
# #   #
#  3@ #
#     #
#23# @#
#32   #
#2    #
#  32 #
#######
 
5 13
#############
#  # 21  @ 3#
##1#@ #  2 2#
#   3    1  #
#############

7 19
###################
#3  1#3 1  3  @#1 #
#2#  @@   @323 1# #
#  3     @  #     #
#  ##23   1#12  21#
# 1#       2#     #
###################
 
9 12
############
#3#23 2  ###
# 31   @  ##
#3  2#3 #3 #
#    2  3 @#
# 1   1  ###
#      2 2 #
# 1  #13  @#
############
 
9 17
#################
# 3 3  212 3 #32#
# 1    2  3 @  ##
#  1        1 1 #
##2 2##1  1#    #
#   @ 2 3   #3  #
#2  1   13      #
#@3  3 3 @ @ 3#@#
#################

12 20
####################
#@@1232#3123123    #
#     ##    #      #
#1 #    #          #
# 2      # #       #
#  3#              #
#3  333 3 3 3 3    #
#@  #  @  3 3@     #
#    # ##          #
# 1 2 1  2 1#2 1 21#
# 3 3 3 3 3#3 3  13#
####################
vndsfjfndjnvfjdnvjv  dnfjvfdjnvfjdngjdffg df j4  3j32h432h4 3h32h4 j32hj32hj32 h4j32h
3 6
######
#1##1#
######
My AC code gives:

Code: Select all

LURD
DL
-1
DRDLURD
RDLULRD
DRURDLDLURU
RLURULURDL
-1
RDLULURDLDRD
RDLDLURDRURD
LDRD
-1
-1
RDLDR
-1
LDRDLUL
RULDRDLDRUL
RDRULURDLD
RDLULRUL
DLUD
-1
LULDLURDRD
DLDRU
DURULDRU
URLDRDLDRDU
-1
My DFS was too slow but BFS works well. Yes, there should be a newline at the end of the last line.