我遇到了这个.
它要求计算在 4x3 网格中可以制作特定长度的锁定图案的方式数，并遵循规则。可能有些点不能包含在路径中
有效的模式具有以下属性：
图案可以使用第一次接触的点序列来表示（与绘制图案的顺序相同），从 (1,1) 到 (2,2) 的图案与图案不同从 (2,2) 到 (1,1)。
对于模式表示中的每两个连续的点 A 和 B，如果连接 A 和 B 的线段经过其他一些点，这些点也必须在序列中并且位于 A 和 B 之前，否则该模式将无效。例如，以 (3,1) 开头然后 (1,3) 的模式表示无效，因为该段经过 (2,2)，而 (2,2) 在 (3,1) 之前没有出现在模式表示中，而正确的该模式的表示形式为 (3,1) (2,2) (1,3)。但模式 (2,2) (3,2) (3,1) (1,3) 是有效的，因为 (2,2) 出现在 (3,1) 之前。
在模式表示中，我们不会多次提及同一点，即使该模式将通过另一个有效段再次触及该点，并且模式中的每个段都必须从该模式没有的一个点到另一个点。之前不要触摸，它可能会经过模式中已经出现的一些点。
模式的长度是模式表示中每两个连续点之间的曼哈顿距离之和。两点 (X1, Y1) 和 (X2, Y2) 之间的曼哈顿距离为 |X1 - X2| + |Y1 - Y2| （其中 |X| 表示 X 的绝对值）。
图案必须至少接触两个点
我的方法是蛮力，循环遍历点，从该点开始并使用递归递减长度直到达到长度零，然后将1添加到组合数。
有没有办法用数学方程来计算它或者有更好的算法？
UPDATE:这就是我所做的，它给出了一些错误的答案！我认为问题在于isOk功能 ！notAllowed是不允许的点的全局位掩码。
bool isOk(int i, int j, int di,int dj, ll visited){
int mini = (i<di)?i:di;
int minj = (j<dj)?j:dj;
if(abs(i-di) == 2 && abs(j-dj) == 2 && !getbit(visited, mini+1, minj+1) )
return false;
if(di == i && abs(j - dj) == 2 && !getbit(visited, i,minj+1) )
return false;
if(di == i && abs(j-dj) == 3 && (!getbit(visited, i,1) || !getbit(visited, i,2)) )
return false;
if(dj == j && abs(i - di) == 2 && !getbit(visited, 1,j) )
return false;
return true;
}
int f(int i, int j, ll visited, int l){
if(l > L) return 0;
short& res = dp[i][j][visited][l];
if(res != -1) return res;
res = 0;
if(l == L) return ++res;
for(int di=0 ; di<gN ; ++di){
for(int dj=0 ; dj<gM ; ++dj){
if( getbit(notAllowed, di, dj) || getbit(visited, di, dj) || !isOk(i,j, di,dj, visited) )
continue;
res += f(di, dj, setbit(visited, di, dj), l+dist(i,j , di,dj));
}
}
return res;
}
