• [1320] Hole of Black

  • 时间限制: 1000 ms 内存限制: 65535 K
  • 问题描述
  • Finally, Wodex met Zero. But Zero wore a mask, so Wodex could not see the face.

    There was a steep cliff between them. So, Wodex could not go to the other side.
    Zero said," I have two games to share with you, if you win, you can go to in front of me, but which game do you like?"
    Wodex," I'd like second one."
    Zero," OK! Later, there will be a map sized of M * M on the top of the steep cliff, and you can only begin at (0, 0), and the entrance to go to my side is at (M - 1, M - 1).
    There are only two possible things in the map, blank space or the wall. Blank space means you can go, but te wall means you can not go. When the game is beginning, I will choose a lattice (a, b) named the black hole. When you go one step, the black hole will spread to the adjacent lattice. When a lattice with the black hole, it means the black hole will never disappear on this lattice. When you begin the game, you will be at (0, 0), and the black hole will be at (a, b), so can you successfully arrive at (M - 1, M - 1)? If you touch the black hole, you will die.
    The first black hole will be possible at the wall, it is the same as at the blank space. But after, the black hole can not spread to the wall, only spread to the blank space.

  • 输入
  • First line contains a integer M (2 <= M <= 100), and then M lines, each line contains M characters, each character only is 'O' or 'X', 'O' means the blank space; 'X' means the wall.
    Last line will contain two numbers a (0 < a < M) and b (0 < b < M),
    You can assume that (0, 0) is must be 'O', and (M - 1, M - 1) is must be 'O'.
    M = 0 means the end of the input, and do not need to output.
  • 输出
  • If Wodex can arrive at (M - 1, M - 1), print the number of steps. Otherwise print 'Wodex lost the game!'.
  • 样例输入
  • 5
    4 0
    2 0
  • 样例输出
  • 8
    Wodex lost the game!
  • 提示
  • 来源
  • Hungar
  • 操作