Code: Select all

```
#include<cstdio>
using namespace std;
#define DIST(a, b, c, d) ((a>=c ? (a-c) : (c-a)) + (b>=d ? (b-d) : (d-b)))
int n, m, gridNum, check1, check2, check3, r1, c1, r2, c2, r3, c3, soln;
bool isVisited[9][9];
void backtrack(int i, int j, int k)
{
if(k<=check1)
{
if(k==check1)
if(i!=r1 || j!=c1)
return;
else;
else if(DIST(i, j, r1, c1)>(check1-k))
return;
}
else if(k<=check2)
{
if(k==check2)
if(i!=r2 || j!=c2)
return;
else;
else if(DIST(i, j, r2, c2)>(check2-k))
return;
}
else if(k<=check3)
{
if(k==check3)
if(i!=r3 || j!=c3)
return;
else;
else if(DIST(i, j, r3, c3)>(check3-k))
return;
}
else
{
if(k==gridNum)
if(i==0 && j==1)
soln++;
else
return;
else if(DIST(i, j, 0, 1)>(gridNum-k))
return;
}
isVisited[i][j] = true;
if(i>0 && !isVisited[i-1][j])
backtrack(i-1, j, k+1);
if(i<m-1 && !isVisited[i+1][j])
backtrack(i+1, j, k+1);
if(j>0 && !isVisited[i][j-1])
backtrack(i, j-1, k+1);
if(j<n-1 && !isVisited[i][j+1])
backtrack(i, j+1, k+1);
isVisited[i][j] = false;
}
int main()
{
int t = 1;
while(scanf("%d %d", &m, &n), m)
{
scanf("%d %d %d %d %d %d", &r1, &c1, &r2, &c2, &r3, &c3);
gridNum = m*n, check1 = m*n/4, check2 = 2*m*n/4, check3 = 3*m*n/4;
soln = 0;
backtrack(0, 0, 1);
printf("Case %d: %d\n", t++, soln);
}
return 0;
}
```