>>611
それは北に三回、東に六回行く場合最短になるから、北、北、北、東、東、東、東、東、東、の順列で考える
P、Qも通れるとした場合最短ルートの数は9!になる。
Pを通る最短経路は3!×5!になる
同様にQも3!×5!になる
PもQも通る最短経路は3!×3!に成るから
9!-{2*3!*5!-3!}が答えになる