fork download

copy

#include <vector>
#include <iostream>
#include <unordered_map>
#include <utility>
#include <sstream>
#include <algorithm>
#define INF 100000007
 
using namespace std;
 
class PathFinding{
public:
    int minTurns(vector<string> board);
};
 
vector<vector<vector<vector<int> > > > DP;
vector<vector<vector<vector<bool> > > > visited;
int AI, AJ, BI, BJ;
 
int dp(int ai, int aj, int bi, int bj, vector<string> &board){
    int m = board.size();
    int n = board[0].size();
    if(ai < 0 || ai >= m || aj < 0 || aj >= n)
        return INF;
    if(bi < 0 || bi >= m || bj < 0 || bj >= n)
        return INF;
    if(ai == bi && aj == bj)
        return INF;
    if(board[ai][aj] == 'X' || board[bi][bj] == 'X')
        return INF;
    if(ai == BI && aj == BJ && bi == AI && bj == AJ)
        return 0;
    if(DP[ai][aj][bi][bj] != INF)
        return DP[ai][aj][bi][bj];
    if(visited[ai][aj][bi][bj])
        return INF;
    visited[ai][aj][bi][bj] = true;
    cout << ai << " " << aj << " " << bi << " " << bj << endl;
    int movex[] = {0, 0, 1, 0, -1, 1, 1, -1, -1};
    int movey[] = {0, 1, 0, -1, 0, 1, -1, 1, -1};
    int ret = INF;
    for (int i = 0; i < 9; ++i)
    {
        int ci = ai + movex[i];
        int cj = aj + movey[i];
        for (int j = 0; j < 9; ++j)
        {
            if(i == 0 && j == 0)
                continue;
            int di = bi + movex[j];
            int dj = bj + movey[j];
            if(ci == bi && cj == bj && di == ai && dj == aj)
                continue;
            ret = min(ret, dp(ci, cj, di, dj, board));
        }
    }
    DP[ai][aj][bi][bj] = ret + 1;
    return DP[ai][aj][bi][bj];
}
 
int minTurns(vector<string> board){
    int m = board.size();
    int n = board[0].size();
    DP.clear();
    DP.resize(m, vector<vector<vector<int> > >(n, vector<vector<int> >(m, vector<int>(n, INF))));
    visited.clear();
    visited.resize(m, vector<vector<vector<bool> > >(n, vector<vector<bool> >(m, vector<bool>(n, false))));
    for (int i = 0; i < board.size(); ++i)
    {
        for (int j = 0; j < board[0].size(); ++j)
        {
            if(board[i][j] == 'A'){
                AI = i;
                AJ = j;
            }
            if(board[i][j] == 'B'){
                BI = i;
                BJ = j;
            }
        }
    }
    int ans = dp(AI, AJ, BI, BJ, board);
    if(ans > INF)
        return -1;
    return ans;
}
 
int main(int argc, char const *argv[])
{
    vector<string> board;
    // board.push_back("A.");
    // board.push_back(".B");
 
    board.push_back("XXXXXXXXX");
    board.push_back("A.......B");
    board.push_back("XXXX.XXXX");
 
    // board.push_back("AB.................X");
    // board.push_back("XXXXXXXXXXXXXXXXXXX.");
    // board.push_back("X..................X");
    // board.push_back(".XXXXXXXXXXXXXXXXXXX");
    // board.push_back("X..................X");
    // board.push_back("XXXXXXXXXXXXXXXXXXX.");
    // board.push_back("X..................X");
    // board.push_back(".XXXXXXXXXXXXXXXXXXX");
    // board.push_back("X..................X");
    // board.push_back("XXXXXXXXXXXXXXXXXXX.");
    // board.push_back("X..................X");
    // board.push_back(".XXXXXXXXXXXXXXXXXXX");
    // board.push_back("X..................X");
    // board.push_back("XXXXXXXXXXXXXXXXXXX.");
    // board.push_back("X..................X");
    // board.push_back(".XXXXXXXXXXXXXXXXXXX");
    // board.push_back("X..................X");
    // board.push_back("XXXXXXXXXXXXXXXXXXX.");
    // board.push_back("...................X");
    // board.push_back(".XXXXXXXXXXXXXXXXXXX");
    cout << minTurns(board) << endl;
    cout << DP[1][6][1][2] << endl;
    return 0;
}
 

In file included from /usr/include/c++/4.3/unordered_map:40,
                 from prog.cpp:3:
/usr/include/c++/4.3/c++0x_warning.h:36:2: error: #error This file requires compiler and library support for the upcoming ISO C++ standard, C++0x. This support is currently experimental, and must be enabled with the -std=c++0x or -std=gnu++0x compiler options.
In file included from /usr/include/c++/4.3/unordered_map:48,
                 from prog.cpp:3:
/usr/include/c++/4.3/type_traits:82: error: template argument 1 is invalid
/usr/include/c++/4.3/type_traits:106: error: template argument 1 is invalid
/usr/include/c++/4.3/type_traits:136: error: expected unqualified-id before '&&' token
In file included from /usr/include/c++/4.3/bits/hashtable.h:55,
                 from /usr/include/c++/4.3/unordered_map:54,
                 from prog.cpp:3:
/usr/include/c++/4.3/tr1_impl/hashtable:223: error: expected ',' or '...' before '&&' token
/usr/include/c++/4.3/tr1_impl/hashtable:223: error: invalid constructor; you probably meant 'std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys> (const std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>&)'
/usr/include/c++/4.3/tr1_impl/hashtable:232: error: expected ',' or '...' before '&&' token
/usr/include/c++/4.3/tr1_impl/hashtable:660: error: expected ',' or '...' before '&&' token
/usr/include/c++/4.3/tr1_impl/hashtable:660: error: prototype for 'std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::_Hashtable(std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>)' does not match any in class 'std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>'
/usr/include/c++/4.3/tr1_impl/hashtable:619: error: candidates are: std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::_Hashtable(const std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>&)
/usr/include/c++/4.3/tr1_impl/hashtable:218: error:                 template<class _Key, class _Value, class _Allocator, class _ExtractKey, class _Equal, class _H1, class _H2, class _Hash, class _RehashPolicy, bool __cache_hash_code, bool __constant_iterators, bool __unique_keys> template<class _InputIterator> std::_Hashtable::_Hashtable(_InputIterator, _InputIterator, typename _Allocator::size_type, const _H1&, const _H2&, const _Hash&, const _Equal&, const _ExtractKey&, const _Allocator&)
/usr/include/c++/4.3/tr1_impl/hashtable:557: error:                 std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::_Hashtable(typename _Allocator::size_type, const _H1&, const _H2&, const _Hash&, const _Equal&, const _ExtractKey&, const _Allocator&)
/usr/include/c++/4.3/tr1_impl/hashtable:714: error: expected ',' or '...' before '&&' token
/usr/include/c++/4.3/tr1_impl/hashtable: In member function 'void std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::swap(std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>)':
/usr/include/c++/4.3/tr1_impl/hashtable:723: error: '__x' was not declared in this scope
In file included from /usr/include/c++/4.3/unordered_map:69,
                 from prog.cpp:3:
/usr/include/c++/4.3/tr1_impl/unordered_map: At global scope:
/usr/include/c++/4.3/tr1_impl/unordered_map:90: error: expected ',' or '...' before '&&' token
/usr/include/c++/4.3/tr1_impl/unordered_map:90: error: invalid constructor; you probably meant 'std::__unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc, __cache_hash_code> (const std::__unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc, __cache_hash_code>&)'
/usr/include/c++/4.3/tr1_impl/unordered_map:147: error: expected ',' or '...' before '&&' token
/usr/include/c++/4.3/tr1_impl/unordered_map:147: error: invalid constructor; you probably meant 'std::__unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc, __cache_hash_code> (const std::__unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc, __cache_hash_code>&)'
/usr/include/c++/4.3/tr1_impl/unordered_map:205: error: expected ',' or '...' before '&&' token
/usr/include/c++/4.3/tr1_impl/unordered_map:205: error: invalid constructor; you probably meant 'std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc> (const std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&)'
/usr/include/c++/4.3/tr1_impl/unordered_map:209: error: expected ',' or '...' before '&&' token
/usr/include/c++/4.3/tr1_impl/unordered_map: In member function 'std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>)':
/usr/include/c++/4.3/tr1_impl/unordered_map:213: error: '__x' was not declared in this scope
/usr/include/c++/4.3/tr1_impl/unordered_map: At global scope:
/usr/include/c++/4.3/tr1_impl/unordered_map:254: error: expected ',' or '...' before '&&' token
/usr/include/c++/4.3/tr1_impl/unordered_map:254: error: invalid constructor; you probably meant 'std::unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc> (const std::unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&)'
/usr/include/c++/4.3/tr1_impl/unordered_map:258: error: expected ',' or '...' before '&&' token
/usr/include/c++/4.3/tr1_impl/unordered_map: In member function 'std::unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& std::unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(std::unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>)':
/usr/include/c++/4.3/tr1_impl/unordered_map:262: error: '__x' was not declared in this scope
/usr/include/c++/4.3/tr1_impl/unordered_map: At global scope:
/usr/include/c++/4.3/tr1_impl/unordered_map:283: error: expected ',' or '...' before '&&' token
/usr/include/c++/4.3/tr1_impl/unordered_map: In function 'void std::swap(std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>)':
/usr/include/c++/4.3/tr1_impl/unordered_map:285: error: '__x' was not declared in this scope
/usr/include/c++/4.3/tr1_impl/unordered_map:285: error: '__y' was not declared in this scope
/usr/include/c++/4.3/tr1_impl/unordered_map: At global scope:
/usr/include/c++/4.3/tr1_impl/unordered_map:290: error: expected ',' or '...' before '&&' token
/usr/include/c++/4.3/tr1_impl/unordered_map: In function 'void std::swap(std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&, std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>)':
/usr/include/c++/4.3/tr1_impl/unordered_map:291: error: '__y' was not declared in this scope
/usr/include/c++/4.3/tr1_impl/unordered_map: At global scope:
/usr/include/c++/4.3/tr1_impl/unordered_map:295: error: expected ',' or '...' before '&&' token
/usr/include/c++/4.3/tr1_impl/unordered_map: In function 'void std::swap(std::unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>)':
/usr/include/c++/4.3/tr1_impl/unordered_map:297: error: '__x' was not declared in this scope
/usr/include/c++/4.3/tr1_impl/unordered_map:297: error: '__y' was not declared in this scope
/usr/include/c++/4.3/tr1_impl/unordered_map: At global scope:
/usr/include/c++/4.3/tr1_impl/unordered_map:302: error: expected ',' or '...' before '&&' token
/usr/include/c++/4.3/tr1_impl/unordered_map: In function 'void std::swap(std::unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&, std::unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>)':
/usr/include/c++/4.3/tr1_impl/unordered_map:303: error: '__y' was not declared in this scope

Standard output is empty