10384 - The Wall Pushers

[Observer]

I got Accepted with a lazy A* code, which runs for ~2 sec. However, I see from the ranklist that many of you managed to solve this problem within 0.1 sec!! So could anyone kindly tell me how you do that? Thanks in advance!

( Is that sth related to BFS + Hash table? I know nothing about hashing, so could anyone show me some reference on that issue? Thx )

[Larry]

I used BFS + Hashing for .38 seconds. If you are careful, you can cache the position of the walls + position.

[Observer]

Hey Larry, could you provide me with some on-line materials on Hashing please? I really want to learn it

[Larry]

I used STL's HashMap.. for this problem, all that matters is that we don't walk to the same states again, since it's always suboptimal.. is that what you mean?

[Observer]

Well, since I'm a Pascal programmer, I can't directly use the classes in STL... (or can I? )

Perhaps there ARE some similar functions/procedures in Pascal. But before I actually find it, it's better for me to know the concept behind hashing and just build the table all my myself...

[Larry]

True O(1) insert/ O(1) query is hard to come by. STL's HashMap is actually not Hash, but a red-black tree (if I'm wrong, it's certainly one of the balanced binary trees..)

You definitely could just write a red-black tree.. it's not so hard.

[UFP2161]

In g++ 2.95 (/usr/include/g++-3/stl_map.h):
[cpp]_Rep_type _M_t; // red-black tree representing map[/cpp]

Though my book on the STL says the standard doesn't actually specify how a map should be represented.

[DD]

Is there any tricky test cases for this problem. I try to solve this problem by using BFS with memorizing to reduce the run time. However I got W.A. several times, please help me
Following is my code:

Code: Select all

#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <set>

using namespace std;

vector<vector<int> > map(4, vector<int>(6));
typedef set<vector<vector<int> > > my_set;
class step
{
    public:
        string path;
        vector<vector<int> > map;
        pair<int, int> loc;
        step(string &path, vector<vector<int> > map, pair<int, int> &loc)
        {
            this->path = path;
            this->map = map;
            this->loc = loc;
        }
};

void swap(int &a, int &b)
{
    int temp;
    temp = a;
    a = b;
    b = temp;
}

void get_data(void)
{
    for(size_t i = 0; i < 4; ++i)
        for(size_t j = 0; j < 6; ++j)
            cin >> map[i][j];
}

pair<int, int> operator + (const pair<int, int> &a, const pair<int, int> &b)
{
    pair<int, int> sum;
    sum.first = a.first + b.first;
    sum.second = a.second + b.second;
    return sum;
}

bool in_map(const pair<int, int> &loc)
{
    if (loc.first >= 0 && loc.first <= 3 && loc.second >= 0 && loc.second <= 5)
        return true;
    else
        return false;
}

void BFS(pair<int, int> &start)
{
    my_set hash_table;
    queue<step> q;
    string temp;
    map[start.first][start.second] |= (1 << 4);
    q.push(step(temp, map, start));
    pair<int, int> shift[4] = {pair<int, int>(0, -1), pair<int, int>(-1, 0), pair<int, int>(0, 1), pair<int, int>(1, 0)};
    char symbol[4] = {'W', 'N', 'E', 'S'};
    int anti_dir[4] = {2, 3, 0, 1};
    while(!q.empty())
    {
        step current = q.front();
        my_set::iterator iter = hash_table.find(current.map);
        if (iter == hash_table.end())
        {
            hash_table.insert(iter, current.map);
            for(size_t dir = 0; dir < 4; ++dir)
            {
                if ((current.map[current.loc.first][current.loc.second] & (1 << dir)) == 0)
                {
                    pair<int, int> next_loc = current.loc + shift[dir];
                    string next_path = current.path + symbol[dir];
                    if (in_map(next_loc) == true)
                    {
                        vector<vector<int> > next_map(current.map);
                        next_map[current.loc.first][current.loc.second] &= ~(1 << 4);
                        next_map[next_loc.first][next_loc.second] |= (1 << 4);
                        q.push(step(next_path, next_map, next_loc));
                    }
                    else
                    {
                        cout << next_path << endl;
                        return;
                    }
                }
                else
                {
                    pair<int, int> next_loc = current.loc + shift[dir];
                    if (in_map(next_loc) == true && (current.map[next_loc.first][next_loc.second] & (1 << dir)) == 0)
                    {
                        string next_path = current.path + symbol[dir];
                        vector<vector<int> > next_map(current.map);
                        next_map[current.loc.first][current.loc.second] &= ~(1 << 4);
                        next_map[current.loc.first][current.loc.second] &= ~(1 << dir);
                        next_map[next_loc.first][next_loc.second] |= (1 << dir);
                        next_map[next_loc.first][next_loc.second] &= ~(1 << anti_dir[dir]);
                        next_map[next_loc.first][next_loc.second] |= (1 << 4);
                        q.push(step(next_path, next_map, next_loc));
                    }
                }
            }
        }
        q.pop();
    }
}

int main(int argc, char *argv[])
{
    pair<int, int> start;
    while((cin >> start.first >> start.second), start.first || start.second)
    {
        --start.first, --start.second;
        swap(start.first, start.second);
        get_data();
        BFS(start);
    }
    return 0;
}



[DD]

I just got A.C. for this problem after I totally reimplemented it. One interesting thing I found is that my reimplementation which used STL queue got T.L.E. first and then passed after I used my own queue in 0.016 secs. This maybe a helpful hint for people who got T.L.E. by using C++.

Is there any tricky test cases for this problem. I try to solve this problem by using BFS with memorizing to reduce the run time. However I got W.A. several times, please help me
Following is my code:

Code: Select all

#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <set>

using namespace std;

vector<vector<int> > map(4, vector<int>(6));
typedef set<vector<vector<int> > > my_set;
class step
{
    public:
        string path;
        vector<vector<int> > map;
        pair<int, int> loc;
        step(string &path, vector<vector<int> > map, pair<int, int> &loc)
        {
            this->path = path;
            this->map = map;
            this->loc = loc;
        }
};

void swap(int &a, int &b)
{
    int temp;
    temp = a;
    a = b;
    b = temp;
}

void get_data(void)
{
    for(size_t i = 0; i < 4; ++i)
        for(size_t j = 0; j < 6; ++j)
            cin >> map[i][j];
}

pair<int, int> operator + (const pair<int, int> &a, const pair<int, int> &b)
{
    pair<int, int> sum;
    sum.first = a.first + b.first;
    sum.second = a.second + b.second;
    return sum;
}

bool in_map(const pair<int, int> &loc)
{
    if (loc.first >= 0 && loc.first <= 3 && loc.second >= 0 && loc.second <= 5)
        return true;
    else
        return false;
}

void BFS(pair<int, int> &start)
{
    my_set hash_table;
    queue<step> q;
    string temp;
    map[start.first][start.second] |= (1 << 4);
    q.push(step(temp, map, start));
    pair<int, int> shift[4] = {pair<int, int>(0, -1), pair<int, int>(-1, 0), pair<int, int>(0, 1), pair<int, int>(1, 0)};
    char symbol[4] = {'W', 'N', 'E', 'S'};
    int anti_dir[4] = {2, 3, 0, 1};
    while(!q.empty())
    {
        step current = q.front();
        my_set::iterator iter = hash_table.find(current.map);
        if (iter == hash_table.end())
        {
            hash_table.insert(iter, current.map);
            for(size_t dir = 0; dir < 4; ++dir)
            {
                if ((current.map[current.loc.first][current.loc.second] & (1 << dir)) == 0)
                {
                    pair<int, int> next_loc = current.loc + shift[dir];
                    string next_path = current.path + symbol[dir];
                    if (in_map(next_loc) == true)
                    {
                        vector<vector<int> > next_map(current.map);
                        next_map[current.loc.first][current.loc.second] &= ~(1 << 4);
                        next_map[next_loc.first][next_loc.second] |= (1 << 4);
                        q.push(step(next_path, next_map, next_loc));
                    }
                    else
                    {
                        cout << next_path << endl;
                        return;
                    }
                }
                else
                {
                    pair<int, int> next_loc = current.loc + shift[dir];
                    if (in_map(next_loc) == true && (current.map[next_loc.first][next_loc.second] & (1 << dir)) == 0)
                    {
                        string next_path = current.path + symbol[dir];
                        vector<vector<int> > next_map(current.map);
                        next_map[current.loc.first][current.loc.second] &= ~(1 << 4);
                        next_map[current.loc.first][current.loc.second] &= ~(1 << dir);
                        next_map[next_loc.first][next_loc.second] |= (1 << dir);
                        next_map[next_loc.first][next_loc.second] &= ~(1 << anti_dir[dir]);
                        next_map[next_loc.first][next_loc.second] |= (1 << 4);
                        q.push(step(next_path, next_map, next_loc));
                    }
                }
            }
        }
        q.pop();
    }
}

int main(int argc, char *argv[])
{
    pair<int, int> start;
    while((cin >> start.first >> start.second), start.first || start.second)
    {
        --start.first, --start.second;
        swap(start.first, start.second);
        get_data();
        BFS(start);
    }
    return 0;
}