I ran into this problem .
which asks to calculate the number of ways in which a blocking pattern of a certain length can be made in a 4x3 grid and follow the rules. maybe some of the points should not be included in the path
A valid template has the following properties:
A pattern can be represented using a sequence of points that it touches for the first time (in the same drawing order), a pattern going from (1,1) to (2,2) is not equal to a pattern coming from (2 , 2) to (1,1).
For every two consecutive points A and B in the pattern view, if the line segment connecting A and B passes through some other points, these points must also be in sequence and are in front of A and B, otherwise the pattern will be invalid. For example, a template view that starts with (3.1), then (1.3) is invalid because the segment goes through (2.2), which did not appear in the template view before (3.1), and the correct View for this figure, (3.1) (2.2) (1.3). But the pattern (2.2) (3.2) (3.1) (1.3) is valid, since (2.2) appeared earlier (3.1).
In the template view, we will not mention the same point more than once, even if the template touches this point again through another valid segment, and each segment in the template must move from a point to another which the template has not touched before, and it could pass through some points that have already appeared in the template.
The length of the pattern is the sum of the Manhattan distances between every two consecutive points in the pattern view. The Manhattan distance between two points (X1, Y1) and (X2, Y2) is | X1 - X2 | + | Y1 - Y2 | (where | X | means the absolute value of X).
The pattern must touch at least two points.
my approach was brute force, the loop over the dots started at the point and used a recursive decrementing length until it reached zero length, and then added 1 to the number of combinations.
?
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;
}