我发现了这个问题。
它要求计算在4x3的网格中制作特定长度锁定图案的方法数,并遵循规则。 有些点可能不能包含在路径中
有效的模式具有以下属性:
一个图案可以用它第一次接触的点的序列来表示(按照绘制图案的顺序),从(1,1)到(2,2)的图案与从(2,2)到(1,1)的图案不同。
对于图案表示中的每两个相邻点A和B,如果连接A和B的线段通过其他点,则这些点也必须在序列中,并且出现在A和B之前,否则该图案将无效。例如,以(3,1)开始然后是(1,3)的图案表示是无效的,因为线段通过(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的绝对值)。
一个图案必须至少接触两个点
更新:这是我所做的,它给出了一些错误的答案!我认为问题在于 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;
}