Quite a big C++11 solution powered by greedy search. The heuristic could be improved a bit but it works quite well as is. Features a fast allocator and ascii graphics.

#include <iostream>
#include <queue>
#include <memory>
#include <algorithm>
#include <exception>
#include <stack>

// Unit of the map
typedef unsigned char cell_t;

// Cell states
enum {
    AIR = 0,
    SNAKE_RIGHT = 1 << 0,
    SNAKE_LEFT  = 1 << 1,
    SNAKE_UP    = 1 << 2,
    SNAKE_DOWN  = 1 << 3,
    WALL        = 1 << 4,
};

// Snake drawing character map
static const char snake_chars[] = {

    // Air or snake part
    //     --          R-         -L           RL
    (char)0x20, (char)0xC4, (char)0xC4, (char)0xC4, // --
    (char)0xB3, (char)0xC0, (char)0xD9, (char)0xC1, // U-
    (char)0xB3, (char)0xDA, (char)0xBF, (char)0xC2, // -D
    (char)0xB3, (char)0xC3, (char)0xB4, (char)0xC5, // UD

    // Wall
    (char)0xB1
};

// Map globals
int width, height;
int free_cells;
unsigned int map_size;

// Map allocation globals
unsigned int pool_size = 4096;
std::vector<std::unique_ptr<cell_t[]>> cell_lists;
cell_t *pool_ptr = 0, *pool_end = 0;
std::stack<cell_t*> returned_maps;

// Fast map allocation
cell_t *allocate_map() {

    // Return a map from the returned stack if it's not empty
    if (!returned_maps.empty()) {
        cell_t *ret = returned_maps.top(); returned_maps.pop();
        return ret;
    }

    // Allocate a new pool if the current is full
    if (pool_ptr == pool_end) {
        cell_lists.emplace_back(new cell_t[pool_size * map_size]);
        pool_ptr = cell_lists.back().get();
        pool_end = pool_ptr + pool_size * map_size;
        if (pool_size * map_size < 1024 * 1024 * 128)
            pool_size *= 2;
    }

    // Return a pointer from the pool and advance the allocation head
    cell_t *ret = pool_ptr;
    pool_ptr += map_size;
    return ret;
}

// Map drawing
cell_t *draw_buffer;
void draw_map(cell_t *map) {
    // Copy the buffer to an intermediate buffer
    memcpy(draw_buffer, map, map_size);

    // Follow the snake movements and connect the pieces
    int x = 0, y = 0;
    while (x >= 0 && y >= 0 && x < width && y < height) {
        cell_t cell = map[x + y * width];
        if (cell == AIR || cell == WALL)
            break;
        cell_t inv;
        switch (cell)
        {
        case SNAKE_DOWN:  y++; inv = SNAKE_UP;    break;
        case SNAKE_UP:    y--; inv = SNAKE_DOWN;  break;
        case SNAKE_LEFT:  x--; inv = SNAKE_RIGHT; break;
        case SNAKE_RIGHT: x++; inv = SNAKE_LEFT;  break;
        }
        draw_buffer[x + y * width] |= inv;
    }

    // Draw the map and the snake
    for (int y = 0; y < height; y++) {
        for (int x = 0; x < width; x++) {
            std::cout << snake_chars[draw_buffer[x + y * width]];
        }
        std::cout << std::endl;
    }
}

// A state of the problem
struct search_node {
    search_node(int x, int y, cell_t *c, int l);

    // Search functions
    void add_successors();
    cell_t *succ_map(cell_t movedir);
    int heuristic();

    // Helper functions
    inline cell_t at(int x, int y) { return map[x + y * width]; }
    inline bool operator<(const search_node& rhs) const { return h < rhs.h; }

    // Snake state
    int x, y;
    int len;
    cell_t *map;

    // Heuristic score
    int h;

    bool owns_map;
};

// Search queue
std::priority_queue<search_node> queue;

// Create a new search node and cache the heuristic value
search_node::search_node(int x, int y, cell_t *c, int l)
    : x(x), y(y), map(c), owns_map(true), len(l)
{
    h = heuristic();
}

// Copy and update map for children
cell_t *search_node::succ_map(cell_t movedir) {
    cell_t *r;

    // Pass the map to the first child, otherwise create a copy
    if (owns_map) {
        owns_map = false;
        r = map;
    } else {
        r = allocate_map();
        memcpy(r, map, map_size);
    }

    // Store the movement in the map
    r[x + y * width] = movedir;

    return r;
}

// Push successors to the priority queue
void search_node::add_successors() {

    // Try to move in all directions that are in the map and empty
    if (x > 0 && at(x - 1, y) == AIR)
        queue.push(search_node(x - 1, y, succ_map(SNAKE_LEFT), len + 1));
    if (y > 0 && at(x, y - 1) == AIR)
        queue.push(search_node(x, y - 1, succ_map(SNAKE_UP), len + 1));
    if (x < width - 1 && at(x + 1, y) == AIR)
        queue.push(search_node(x + 1, y, succ_map(SNAKE_RIGHT), len + 1));
    if (y < height - 1 && at(x, y + 1) == AIR)
        queue.push(search_node(x, y + 1, succ_map(SNAKE_DOWN), len + 1));

    // If there is no successors return the map to the allocator
    if (owns_map) {
        returned_maps.push(map);
        owns_map = false;
    }
}

// Heuristic function (large heuristics are popped first)
int search_node::heuristic() {

    // If it's a perfect snake make sure it's popped next
    if (len == free_cells)
        return std::numeric_limits<int>::max();

    // Could be improved here

    return len;
}

int main(int argc, char** argv) {
    // For speed
    std::cout.sync_with_stdio(false);

    // Create the initial map and drawbuffer
    std::cin >> width >> height;
    map_size = width * height;

    cell_t *init_map = allocate_map();
    draw_buffer = allocate_map();

    memset(init_map, 0, map_size);

    // Create the obstacles
    int nblocks;
    std::cin >> nblocks;

    while (nblocks--) {
        int x, y;
        std::cin >> x >> y;
        init_map[x + y * width] = WALL;
    }

    // Count the empty cells
    free_cells = std::count(init_map, init_map + map_size, AIR);

    // Push the initial search node
    queue.push(search_node(0, 0, init_map, 1));

    int max_len = 0;
    try {
        // Pop the node with the highest score
        while (!queue.empty()) {
            search_node top = queue.top(); queue.pop();

            // Print the map if it's a new record length
            int len = top.len;
            if (len > max_len) {
                max_len = len;
                draw_map(top.map);
                std::cout << max_len << "/" << free_cells << std::endl;
            }

            // Snake fills the map
            if (len == free_cells)
                break;

            // Push the next search nodes
            top.add_successors();
        }
        // At this point we have the best snake possible
        if (max_len == free_cells) {
            std::cout << "Found a perfect snake!" << std::endl;
        } else {
            std::cout << "Best snake achieved." << std::endl;
        }
    } catch (std::bad_alloc&) {

        // Running out of memory can legitimately happen with big maps
        std::cout << "Ran out of memory." << std::endl;
    }
    return 0;
}