题目：https://loj.ac/problem/2550
只会写20分的搜索……
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
int n,m,ans;
bool b[N][N],vis[N][N];
void dfs(int x,int y,bool fx,int lj)
{
if(y>m)y=; if(x>n)x=;
if(vis[x][y])
{
if(x==&&y==)
{
bool fg=;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
if(!vis[i][j]){fg=;break;}
if(!fg)ans+=lj;
}
return;
}
if(b[x][y])fx=; if(!fx)lj++;
vis[x][y]=;
dfs(x+,y,fx,lj); dfs(x,y+,fx,lj);
vis[x][y]=;
}
int main()
{
int T;scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
scanf("%1d",&b[i][j]);
ans=;
dfs(,,,);
printf("%d\n",ans);
}
return ;
}
观察多篇题解：
https://blog.csdn.net/qq_39972971/article/details/80441415
https://www.cnblogs.com/cjyyb/p/10422074.html
https://blog.csdn.net/scar_lyw/article/details/80411617
由结论可知合法的方案取决于左上角 d*d 怎么决策。（副对角线可以拐，所以是 d 条而不是 2*d-1 条）
枚举 d*d 里向下 i 步，向右 j=d-i 步，那么需要 i 和 n 互质、 j 和 m 互质。这样就是合法方案。考虑已知 i , j ，算贡献。
每个位置 ( x, y ) 都会在 “一轮”（d步） 之后走到 ( x+i , y+j ) 。
( 1, 1 ) 位置第一轮走到 ( i+1 , j+1 ) 。考虑 DP 这个第一轮的走法，就知道全局的走法了。
( 1, 1 ) 只能向下走或向右走。走过位置 ( x, y ) ，意味着会在之后的轮中把 ( x+k*i , y+k*j ) 都走过。
把 “走到第一个障碍为止的步数” 改成 “走到每个障碍为止的步数中的最小值” ， 一个位置 ( x, y ) 的权值就是所有 ( x+k*i , y+k*j ) 的是障碍的点的 “走到该点的步数最小值” 取 min ；
就是要 DP 一条从 ( 1, 1 ) 到 ( i+1 , j+1 ) 的只能向下或向右走的路径，该路径贡献是路径上各点权值的最小值。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
int Mn(int a,int b){return a<b?a:b;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
const int N=,M=N*N,mod=;
int upt(int x){while(x>=mod)x-=mod;while(x<)x+=mod;return x;} int n,m,lm,c[N][N],dp[N][N][M],ans;
bool b[N][N];
void cz(int &x,int y){x=upt(x+y);}
void solve(int x,int y)
{
memset(dp,,sizeof dp);
dp[][][c[][]]=;
for(int i=;i<=x+;i++)
for(int j=;j<=y+;j++)
for(int k=;k<=lm;k++)
{
int tp=dp[i][j][k]; if(!tp)continue;
if(i<=x)cz(dp[i+][j][Mn(k,c[i+][j])],tp);
if(j<=y)cz(dp[i][j+][Mn(k,c[i][j+])],tp);
}
for(int k=;k<=lm;k++)
ans=(ans+(ll)k*dp[x+][y+][k])%mod;
}
int main()
{
int T;scanf("%d",&T);
while(T--)
{
ans=;
scanf("%d%d",&n,&m); lm=n*m;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
scanf("%1d",&b[i][j]);
int g=gcd(n,m);
for(int x=;x<g;x++)
{
int y=g-x;
if(gcd(x,n)!=||gcd(y,m)!=)continue;
for(int i=;i<=x+;i++)
for(int j=;j<=y+;j++)
{
int d=i+j-;
if(b[i][j]){c[i][j]=d;continue;}
int tx=i+x, ty=j+y; d+=g;
if(tx>n)tx-=n; if(ty>m)ty-=m;
while()
{
if(b[tx][ty]||(tx==i&&ty==j))
{c[i][j]=d;break;}
tx+=x; ty+=y; d+=g;
if(tx>n)tx-=n;if(ty>m)ty-=m;
}
}
solve(x,y);
}
printf("%d\n",ans);
}
return ;
}