正反则难，用所有方案数减去不符合条件的方案数（即任意两个相邻的格子互不相同），还有就是要注意这次并非环形排列，那么这个题就做完了

$Ans=m^n-m·(m-1)^{n-1}$