The problem

I am trying to solve a competitive programming problem which goes like that:

Given an m x n rectangular grid, what the maximum number of cars than can be parked (each car takes 1 cell) so that each car has a path to the entrance (the top left corner).

The time / memory restrictions are 64 MB and 1 sec.

UPDATE

1. 2 <= m, n <= 7 (otherwise restrictions have no meaning)
2. I'm rather more interested in Brute Force solutions alike the proposed one that include searching over solution space with some pruning / heuristics

** UPDATE 2 **

On one of the competitive programming websites, this problem is categorized under the BFS topic (I'm not sure whether it's BFS in terms of the solution space, or rather the parking lot itself... if the latter even makes sense)

Attempted algorithm

The plain brute-force is not possible because of 2^49 size of the solution space. I tried to anize a brute-force DFS search using a recursive function f(x) where x is the index of the cells still available, so that on each call cells [0, x) are already set and cells [x, m * n) are still to be set by this call. The board/parking lot is in the global variable board and is updated by each call accordingly.

In the beginning of each f() call, I try to prune the search by running a DFS over all empty cells and measuring the number of accessible cars dfsCars and the maximum index of an accessible cell. So I prune if:

• not all cars are accessible cars > dfsCars
• maximum available index is less than the current cell maxDfs < x
• even if all the available cells [x, maxDfs + 1) to be parked onto, we'll not improve the current best cars + maxDfs + 1 - x < maxCars

Actually I'm content with the current results, as I pass around 45/50 of the provided tests, and the running times on the verbose screenshot which I've provided below seem legit.

Unfortunately I still don't fit into the requirements, so would you please help me with a piece of advice or any other approach that would work better?

I guess I spend too much time on DFS-ing when checking connectivity (the reason for doing is hoping that pruning will save more time). I also checked the Dynamic Connectivity algorithms (delete-only) but I haven't tried it yet, perhaps it could help in checking accessibility faster. Also I think it might be better to run DFS-accessibility check only when a new car is added (marked 1) instead of at the beginning of each f() call.

Code

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>

#define MAXLEN 7
#define MOVES 4

int m, n;
char board[MAXLEN][MAXLEN] = {0};
char tmp[MAXLEN][MAXLEN] = {0};
int cnt = 0;
int cars = 0;

int maxDfs;
int dfsCars;

int maxCars = -1;

clock_t begin;


void printBoard() {
    ++cnt;
    for (int i = 0; i != m; ++i) {
        for (int j = 0; j != n; ++j)
            putchar(board[i][j] ? 'o' : '.');
        puts("");
    }
    printf("\tcars = %d", cars);
    puts("");
}

void dfs(int i, int j) {
    if (i < 0 || i >= m)
        return;
    if (j < 0 || j >= n)
        return;

    if (tmp[i][j] == 1) {
        tmp[i][j] = 2;
        ++dfsCars;
        return;
    }
    if (tmp[i][j] != 0)
        return;

    tmp[i][j] = -1;
    if (i * n + j > maxDfs)
        maxDfs = i * n + j;

    dfs(i, j - 1);
    dfs(i, j + 1);
    dfs(i - 1, j);
    dfs(i + 1, j);

}

void f(int x) {

    // [x, m * n)
    if (m * n - x + cars <= maxCars)
        return;

    int ix = x / n;
    int jx = x % n;

    for (int i = 0; i != m; ++i)
        for (int j = 0; j != n; ++j)
            tmp[i][j] = board[i][j];
    maxDfs = -1;    // sentinel


    // !!!
    // check accessibility of all the cars

    // dfs over all the emtpy spaces starting from the entrance
    // dfsCars = # of accessible cars
    dfsCars = 0;
    dfs(0, 0);
    // dfs(m - 1, n - 1);
    if (dfsCars != cars)
        return;

    // the position is valid

    // printBoard();
    if (maxCars < cars) {
        clock_t end = clock();
        double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;

        maxCars = cars;

        printf("%14.9f: %d new max!\n",
               time_spent, maxCars);
    }

    if (x == m * n) {
        return;
    }

    // [x, maxDfs]
    // maxDfs + 1 - x
    if (maxDfs < x)
        return;
    if (maxDfs + 1 - x + cars <= maxCars)
        return;

    bool ijOk = tmp[ix][jx] == -1;
    // dfs => stops at z < x
    // => prune
    // printf("maxDfs = %d\n", maxDfs);

    board[ix][jx] = 0;
    f(x + 1);

    if (ijOk) {
        board[ix][jx] = 1;
        ++cars;

        f(x + 1);
        board[ix][jx] = 0;
        --cars;
    }

}

int main()
{
    scanf("%d%d", &m, &n);
    // m = 2;
    // n = 3;


    begin = clock();

    f(0);

    printf("%d\n", maxCars);
    // printf("%d\n", cnt);
    return 0;
}

Sample run

In this run I was starting DFS from (m - 1, n - 1) hoping that it could improve the running time:

7 7
   0.000000000: 0 new max!
   0.000000000: 1 new max!
   0.000000000: 2 new max!
   0.000000000: 3 new max!
   0.000000000: 4 new max!
   0.000000000: 5 new max!
   0.000000000: 6 new max!
   0.000000000: 7 new max!
   0.001000000: 8 new max!
   0.004000000: 9 new max!
   0.008000000: 10 new max!
   0.019000000: 11 new max!
   0.036000000: 12 new max!
   0.080000000: 13 new max!
   0.207000000: 14 new max!
   0.430000000: 15 new max!
   0.678000000: 16 new max!
   0.999000000: 17 new max!
   1.392000000: 18 new max!
   2.660000000: 19 new max!
   4.974000000: 20 new max!
  25.279000000: 21 new max!
  64.884000000: 22 new max!
 128.093000000: 23 new max!
 265.674000000: 24 new max!
 442.824000000: 25 new max!
 843.028000000: 26 new max!

The problem

I am trying to solve a competitive programming problem which goes like that:

Given an m x n rectangular grid, what the maximum number of cars than can be parked (each car takes 1 cell) so that each car has a path to the entrance (the top left corner).

The time / memory restrictions are 64 MB and 1 sec.

UPDATE

1. 2 <= m, n <= 7 (otherwise restrictions have no meaning)
2. I'm rather more interested in Brute Force solutions alike the proposed one that include searching over solution space with some pruning / heuristics

** UPDATE 2 **

On one of the competitive programming websites, this problem is categorized under the BFS topic (I'm not sure whether it's BFS in terms of the solution space, or rather the parking lot itself... if the latter even makes sense)

Attempted algorithm

The plain brute-force is not possible because of 2^49 size of the solution space. I tried to anize a brute-force DFS search using a recursive function f(x) where x is the index of the cells still available, so that on each call cells [0, x) are already set and cells [x, m * n) are still to be set by this call. The board/parking lot is in the global variable board and is updated by each call accordingly.

In the beginning of each f() call, I try to prune the search by running a DFS over all empty cells and measuring the number of accessible cars dfsCars and the maximum index of an accessible cell. So I prune if:

• not all cars are accessible cars > dfsCars
• maximum available index is less than the current cell maxDfs < x
• even if all the available cells [x, maxDfs + 1) to be parked onto, we'll not improve the current best cars + maxDfs + 1 - x < maxCars

Actually I'm content with the current results, as I pass around 45/50 of the provided tests, and the running times on the verbose screenshot which I've provided below seem legit.

Unfortunately I still don't fit into the requirements, so would you please help me with a piece of advice or any other approach that would work better?

I guess I spend too much time on DFS-ing when checking connectivity (the reason for doing is hoping that pruning will save more time). I also checked the Dynamic Connectivity algorithms (delete-only) but I haven't tried it yet, perhaps it could help in checking accessibility faster. Also I think it might be better to run DFS-accessibility check only when a new car is added (marked 1) instead of at the beginning of each f() call.

Code

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>

#define MAXLEN 7
#define MOVES 4

int m, n;
char board[MAXLEN][MAXLEN] = {0};
char tmp[MAXLEN][MAXLEN] = {0};
int cnt = 0;
int cars = 0;

int maxDfs;
int dfsCars;

int maxCars = -1;

clock_t begin;


void printBoard() {
    ++cnt;
    for (int i = 0; i != m; ++i) {
        for (int j = 0; j != n; ++j)
            putchar(board[i][j] ? 'o' : '.');
        puts("");
    }
    printf("\tcars = %d", cars);
    puts("");
}

void dfs(int i, int j) {
    if (i < 0 || i >= m)
        return;
    if (j < 0 || j >= n)
        return;

    if (tmp[i][j] == 1) {
        tmp[i][j] = 2;
        ++dfsCars;
        return;
    }
    if (tmp[i][j] != 0)
        return;

    tmp[i][j] = -1;
    if (i * n + j > maxDfs)
        maxDfs = i * n + j;

    dfs(i, j - 1);
    dfs(i, j + 1);
    dfs(i - 1, j);
    dfs(i + 1, j);

}

void f(int x) {

    // [x, m * n)
    if (m * n - x + cars <= maxCars)
        return;

    int ix = x / n;
    int jx = x % n;

    for (int i = 0; i != m; ++i)
        for (int j = 0; j != n; ++j)
            tmp[i][j] = board[i][j];
    maxDfs = -1;    // sentinel


    // !!!
    // check accessibility of all the cars

    // dfs over all the emtpy spaces starting from the entrance
    // dfsCars = # of accessible cars
    dfsCars = 0;
    dfs(0, 0);
    // dfs(m - 1, n - 1);
    if (dfsCars != cars)
        return;

    // the position is valid

    // printBoard();
    if (maxCars < cars) {
        clock_t end = clock();
        double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;

        maxCars = cars;

        printf("%14.9f: %d new max!\n",
               time_spent, maxCars);
    }

    if (x == m * n) {
        return;
    }

    // [x, maxDfs]
    // maxDfs + 1 - x
    if (maxDfs < x)
        return;
    if (maxDfs + 1 - x + cars <= maxCars)
        return;

    bool ijOk = tmp[ix][jx] == -1;
    // dfs => stops at z < x
    // => prune
    // printf("maxDfs = %d\n", maxDfs);

    board[ix][jx] = 0;
    f(x + 1);

    if (ijOk) {
        board[ix][jx] = 1;
        ++cars;

        f(x + 1);
        board[ix][jx] = 0;
        --cars;
    }

}

int main()
{
    scanf("%d%d", &m, &n);
    // m = 2;
    // n = 3;


    begin = clock();

    f(0);

    printf("%d\n", maxCars);
    // printf("%d\n", cnt);
    return 0;
}

Sample run

In this run I was starting DFS from (m - 1, n - 1) hoping that it could improve the running time:

7 7
   0.000000000: 0 new max!
   0.000000000: 1 new max!
   0.000000000: 2 new max!
   0.000000000: 3 new max!
   0.000000000: 4 new max!
   0.000000000: 5 new max!
   0.000000000: 6 new max!
   0.000000000: 7 new max!
   0.001000000: 8 new max!
   0.004000000: 9 new max!
   0.008000000: 10 new max!
   0.019000000: 11 new max!
   0.036000000: 12 new max!
   0.080000000: 13 new max!
   0.207000000: 14 new max!
   0.430000000: 15 new max!
   0.678000000: 16 new max!
   0.999000000: 17 new max!
   1.392000000: 18 new max!
   2.660000000: 19 new max!
   4.974000000: 20 new max!
  25.279000000: 21 new max!
  64.884000000: 22 new max!
 128.093000000: 23 new max!
 265.674000000: 24 new max!
 442.824000000: 25 new max!
 843.028000000: 26 new max!

• c
• graph-theory
• mathematical-optimization
• depth-first-search

• 4 This question might be a better candidate to Code Review. – karlphillip Commented Feb 16 at 14:55
• 2 @karlphillip is correct, but before posting on Code Review please read A guide to Code Review for Stack Overflow users and How do I ask a good question? first. If you post on Code Review you should delete this question. – pacmaninbw Commented Feb 16 at 15:06
• 1 @karlphillip I've read the links provided, I think yes, it's a valid candidate to Code Review, I'll try to initiate the migration (I guess with <250 reputation I need to flag it for migration first) – Andrey Surovtsev Commented Feb 16 at 17:39
• 1 "2^49 size of the solution space.": where does this number come from? Surely it would depend on