## 11391 - Blobs in the Board

Moderator: Board moderators

RC's
Learning poster
Posts: 65
Joined: Fri Jul 13, 2007 3:17 pm

### 11391 - Blobs in the Board

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 ??

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Code: Select all

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

...
2..
1..

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

RC's
Learning poster
Posts: 65
Joined: Fri Jul 13, 2007 3:17 pm
sorry... it was my foolishness.. I think it can only move 4 directions..
thanks, rio..

jvimal
New poster
Posts: 16
Joined: Tue May 08, 2007 6:27 pm

### TLE?

Will the naive 2**16 * 8 algorithm work? It gets TLEd for me

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Make sure that your code do not do the calculations more than once.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

jvimal
New poster
Posts: 16
Joined: Tue May 08, 2007 6:27 pm
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].

RC's
Learning poster
Posts: 65
Joined: Fri Jul 13, 2007 3:17 pm
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
``````

tanaeem
New poster
Posts: 26
Joined: Mon Mar 12, 2007 6:58 pm
Location: BUET
Contact:
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
``````

Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

### Re: 11391 - Blobs in the Board

Code: Select all

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

``````

Farsan
New poster
Posts: 34
Joined: Fri Aug 12, 2011 6:37 am

### Re: 11391 - Blobs in the Board

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

jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

### Re: 11391 - Blobs in the Board

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