Page 1 of 1

### 11391 - Blobs in the Board

Posted: Mon Jan 14, 2008 7:19 am
The initial position of the board should be like this

Code: Select all

``````..1
23.
...
``````
with . is empty space on the board and numbers represent blobs

I wonder how the number of goals is 2.. I think the answer should be 1, that is 2 jumps over 3, so that the board will be

Code: Select all

``````..1
..2
...
``````
and then after that, 1 jumps over 2..

Are there any other possibilities ??

Posted: Mon Jan 14, 2008 7:22 am

Code: Select all

``````..1
23.
...

...
2..
1..

1..
...
...
``````
-----
Rio

Posted: Mon Jan 14, 2008 7:25 am
sorry... it was my foolishness.. I think it can only move 4 directions..
thanks, rio..

### TLE?

Posted: Mon Jan 14, 2008 7:47 am
Will the naive 2**16 * 8 algorithm work? It gets TLEd for me

Posted: Mon Jan 14, 2008 9:20 am
Make sure that your code do not do the calculations more than once.

Posted: Mon Jan 14, 2008 9:22 am
Observer wrote:Make sure that your code do not do the calculations more than once.
Yeah, I made sure of that. But, it didnt strike me that the memoization could be done on [r][c][State]. Initially I had just done [State].

Posted: Mon Jan 14, 2008 10:44 am
What is the output of this input :

Code: Select all

``````1
4 4 15
1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
3 1
3 2
3 3
3 4
4 1
4 2
4 3
``````

Posted: Mon Jan 14, 2008 1:02 pm
RC's wrote:What is the output of this input :

Code: Select all

``````1
4 4 15
1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
3 1
3 2
3 3
3 4
4 1
4 2
4 3
``````
My ac code gives following output

Code: Select all

``````Case 1: 32090916
``````

### Re: 11391 - Blobs in the Board

Posted: Mon Sep 13, 2010 1:19 pm

Code: Select all

``````
code removed got acc after 16 submission

``````

### Re: 11391 - Blobs in the Board

Posted: Fri May 23, 2014 11:07 am
WA... used dp states as dp[no of jumps completed ][current board state ]

Code: Select all

``````ACED... could not determine the states correctly at first
``````

### Re: 11391 - Blobs in the Board

Posted: Tue Jun 30, 2015 4:40 pm
Why WA? Any more test cases?

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;
}
``````