Блог пользователя OmaeWaMouShenDeiru

Hard problem on UVA !!
Автор OmaeWaMouShenDeiru, 10 лет назад, По-английски

Any ideas of how to solve this problem ??

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
      • »
        »
        »
        »
        10 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

        My code

        → Ответить
        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

          → Ответить
        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
          ← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

          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 ;)

          → Ответить