Code: Select all
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long ul;
typedef bitset<16> bset;
typedef long long ll;
#define UNVISITED -1
int R, C, N;
int RC;
void toCoord(int index, int * i, int * j){
*i = index/C;
*j = index%C;
}
int toIndex(int i, int j){
int ret = i*C + j;
// if(ret >= RC){
// printf("RC is %d\n", RC);
// printf("%d %d is index %d\n", i,j,ret);
// printf("yolo\n");
// exit(0);
// }
return i*C + j;
}
int dx[] = {0,1,1,1,0,-1,-1,-1};
int dy[] = {-1,-1,0,1,1,1,0,-1};
ll arr[1<<16][4][4];
vector<vector<int>> grid, dummy_grid;
void fillGrid(bset bs){
for(int index = 0; index<RC; index++){
int i, j;
toCoord(index, &i, &j);
grid[i][j] = bs[index];
}
}
bset get_bset(){
bset bs;
int index = 0;
for(int i = 0; i<R; i++){
for(int j = 0; j<C; j++){
bs[index] = grid[i][j];
index++;
}
}
return bs;
}
void printBS(bset bs){
for(int i = 0; i<R; i++){
for(int j = 0; j<C; j++){
cout << bs[toIndex(i,j)] << " ";
}
printf("\n");
}
}
void printGrid(){
for(int i = 0; i<R; i++){
for(int j = 0; j<C; j++){
printf("%d ", grid[i][j]);
}
printf("\n");
}
}
ll f(bset bs){
ul ulong = bs.to_ulong();
int bits_set = bs.count();
if(arr[ulong][R-1][C-1] != UNVISITED){
// printf("Memoized. Returning %lld\n", arr[ulong][R-1][C-1]);
return arr[ulong][R-1][C-1];
}
if(bits_set == 1){
// printf("1. Returning 1.\n");
return arr[ulong][R-1][C-1] = 1;
}
bset dummy_bs = get_bset();
fillGrid(bs);
// printf("BS check:\n");
// printBS(bs);
// printf("Grid check:\n");
// printGrid();
// printf("=\n");
ll ret = 0;
for(int i = 0; i<R; i++){
for(int j = 0; j<C; j++){
if(grid[i][j]){
for(int dir = 0; dir<8; dir++){
int I = i + dy[dir];
int J = j + dx[dir];
if(I<0 || J<0 || I>=R || J>=C){
continue;
}
if(grid[I][J]){
int destI = I + dy[dir];
int destJ = J + dx[dir];
if(destI<0 || destJ<0 || destI>=R || destJ>=C){
continue;
}
if(grid[destI][destJ]){
continue;
}
// printf("Original is:\n");
// printGrid();
// printf("-\n");
// if(dir == 3 && i == 0 && j == 0){
// printf("%d %d %d\n", grid[i][j],grid[I][J], grid[destI][destJ]);
// }
grid[i][j] = 0;
grid[I][J] = 0;
grid[destI][destJ] = 1;
bset new_bs = get_bset();
grid[i][j] = 1;
grid[I][J] = 1;
grid[destI][destJ] = 0;
// printf("new bs check:\n");
// printBS(new_bs);
// printf("xxx\n");
// // printf("Jumping %d %d from dir %d\n",i,j, dir);
// printf("From %d %d dir %d skipping %d %d to %d %d\n", i,j, dir, I, J, destI, destJ);
ll this_ret = f(new_bs);
ret += this_ret;
}
}
}
}
}
// grid = dummy_grid;
fillGrid(dummy_bs);
// printf("Returning %lld\n", ret);
// printf("Grid:\n");
// printGrid();
// printf("BS:\n");
// printBS(bs);
// printf("Shouldve been restored\n");
return arr[ulong][R-1][C-1] = ret;
}
int main(){
// bset x;
// for(int y = 0; y<12; y++){
// x[y] = 1;
// }
// cout << x << endl;
// cout << x.to_ulong() << endl;
// return 0;
// int limit = 1<<16;
// for(int x = 0; x<limit; x++){
// arr[x] = UNVISITED;
// }
for(int r = 0; r<4; r++){
for(int c = 0; c<4; c++){
int limit = 1<<r*c;
for(int i = 0; i<limit; i++){
arr[i][r][c] = UNVISITED;
}
}
}
int cases;
scanf("%d", &cases);
for(int e = 0; e<cases; e++){
bset bs;
scanf("%d %d %d", &R, &C, &N);
// printf("Scanned %d %d %d\n", R,C,RC);
for(int x = 0; x<N; x++){
int i, j;
scanf("%d %d", &i, &j);
i--;
j--;
int index = toIndex(i,j);
bs[index] = 1;
// printf("Setting index as %d\n", index);
}
int num_states = 1<<RC;
grid.assign(R, vector<int>(C));
// dummy_grid.assign(R, vector<int>(C));
ll ret = f(bs);
printf("Case %d: %lld\n", e+1, ret);
}
return 0;
}