ProjectEuler 313 Sliding game - 拼圖

313. Sliding game

http://projecteuler.net/index.php?section=problems&id=313


在「滑動」這遊戲中，硬幣籌碼可能會被水平或垂直的移動到棋盤的空格中。

這遊戲的目標就是把紅色籌碼從最左上角的格子移動到最右下角的格子，遊戲最初的空格

都是在棋盤的最右下角。

舉例來說，下圖就是起始於一個 2 * 2 的棋盤，總共只需花費5步就能完成目標。


　┌─┬─┐　　　　　　┌─┬─┐　　　　　　┌─┬─┐
　│●│●│　　　　　　│●│●│　　　　　　│　│●│
　├─┼─┤　第一步→　├─┼─┤　第二步→　├─┼─┤　第三步→
　│●│　│　　　　　　│　│●│　　　　　　│●│●│
　└─┴─┘　　　　　　└─┴─┘　　　　　　└─┴─┘

　┌─┬─┐　　　　　　┌─┬─┐　　　　　　┌─┬─┐
　│●│　│　　　　　　│●│●│　　　　　　│●│●│
　├─┼─┤　第四步→　├─┼─┤　第五步→　├─┼─┤　完成！
　│●│●│　　　　　　│●│　│　　　　　　│　│●│
　└─┴─┘　　　　　　└─┴─┘　　　　　　└─┴─┘

用 S(m,n) 來表示在一個 m * n 的棋盤上完成「滑動」目標所需的的最小步數。

例如 S(5,4) = 25　即 5 * 4 的棋盤只要25步就可以完成。


在 p < 100 且 p 為質數的條件下，可以找到5482種棋盤，且S(m,n) = p^2。


那在 p < 10^6 且 p 為質數的條件下，可以找到幾種棋盤，且S(m,n) = p^2？

--