OmaeWaMouShenDeiru's blog

Hard problem on UVA !!
By OmaeWaMouShenDeiru, 10 years ago, In English

Any ideas of how to solve this problem ??

http://uva.onlinejudge.org/external/100/10085.html

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The total number of states is 9!, and there are at most 4 moves to be made at each state, so it's possible to do a complete search with a BFS.

The constant factor for this approach is rather high, but it should work under the time limit if done carefully.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I tried to use BFS but I don't understand when will I reach "The Most Distant State"

    Should i push the string containing the path along with a vector of the 9 states, is it good enough for the time limit ??

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If you do the following:

      • set up deque for states
      • pick up state on one end (front)
      • create 4 new states out of it, with move counter increased by one
      • check if they are visited (with some other data structure)
      • push unvisited states to the other end of deque (back).

      Question — wouldn't the last item on the deque be the one you need? so you can just take amount from move counter of last item on the deque and this should be the result.

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      If you do a BFS, the states will be visited by increasing distance from the initial state, so the one you're looking for will always be the last one you visit.

      You can check if a state has been visited by using a map in C++. And you can store both the state and the history of moves using strings.

      I coded it that way and it got accepted.

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        This is all i could come up with, but it does not even give correct sample:

        My code

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Inside your BFS, when you try the 4 possibles moves, after you swap the zero with an adjacent element and push the state to the queue, you forgot to swap again to return the array to its original state. Add that swap and you'll get accepted.

          → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
          ← Rev. 4   Vote: I like it 0 Vote: I do not like it

          Oh, and next time, please paste your code in pages like pastebin or ideone and post the link in your comment instead of the whole source code. It will save you lots of downvotes ;)

          → Reply