Topcoder Inv 2001 Semi A+B 500 pointer

Tothello.cpp

#include <bits/stdc++.h>

#define mp make_pair
#define vstr vector<string>
#define pb push_back
#define all(x) begin(x), end(x)

#define sz(x) int(x.size())
#define P(X) cout << X << "\t"
#define NL cout << endl
#define FOR(I,N) for(int I = 0; I < N; ++I)

using namespace std;

typedef pair<int, int> Coord;
typedef pair<int, int> Incr;
static constexpr Incr UP = mp(-1, 0), DN = mp(1, 0), LT = mp(0, -1), RT = mp(0, 1);
static constexpr Incr NE = mp(-1, 1), NW = mp(-1, -1), SE = mp(1, 1), SW = mp(1, -1);

template<typename T> struct Iter2d
{
    #define x second
    #define y first
    vector<vector<T>> *pv;
    Incr incr;
    Coord pos;
    
    Iter2d():pv(NULL){}
    Iter2d(vector<vector<T>> &v1, const Coord &pos1, const Incr &incr1 = RT):pv(&v1), incr(incr1), pos(pos1) {}
    
    Iter2d& operator=(const Iter2d& o)        {pv = o.pv; incr = o.incr; pos = o.pos; return *this;}
    T &operator*()                            {return (*pv)[pos.y][pos.x];}
    Iter2d operator()(Incr i)           const {return Iter2d(*pv, pos, i);}
    operator bool()                     const {return pos.y >= 0 && pos.x >= 0 && pos.y < w() && pos.x < h();}
    bool operator<(const Iter2d &o)     const {return (!incr.y || (pos.y < o.pos.y)) && (!incr.x || (pos.x < o.pos.x));}
    bool operator ==(const Iter2d &o)   const {return o.pos.y == pos.y && o.pos.x == pos.x;}
    bool operator !=(const Iter2d &o)   const {return !(o == *this);}
    
    Iter2d &operator++() 
    { 
        pos.y += incr.y; pos.y = min(pos.y, h()); pos.y = max(pos.y, -1);
        pos.x += incr.x; pos.x = min(pos.x, w()); pos.x = max(pos.x, -1);
        return *this; 
    }
    
    Iter2d next() { Iter2d it = *this; return ++it;}
    int h() const { return pv->size(); }
    int w() const { return ((*pv)[0]).size(); } 
    
    int distance(const Iter2d &o) const 
    { 
        int count = 0;
        Iter2d ite = *this;
        while(ite != o) {++ite; ++count;}
        return count;
    }
    
    Iter2d end() const 
    {
        Iter2d ite = *this;
        while(ite.pos.y >=0 && ite.pos.y < h() && ite.pos.x >= 0 && ite.pos.x < w()) ++ite;
        return ite;
    }
    
    typedef typename vector<T>::difference_type difference_type; 
    typedef typename vector<T>::value_type value_type; 
    typedef typename vector<T>::reference reference; 
    typedef typename vector<T>::pointer pointer; 
    typedef typename vector<T>::iterator::iterator_category iterator_category; 
    #undef x
    #undef y
};

struct Tothello
{
    typedef vector<vector<int>> Board;
    Board board;
    
    int doCount(const Board &b)
    {
        int cnt = 0;
        FOR(i, 8) cnt += count(all(b[i]), 1);
        return cnt;
    }
    
    int applyone(Board &b, const Coord &c, const Incr &i1, const Incr &i2)
    {
        int cnt = 0;
        for(Iter2d<int> it(b, c, i1), ite = it.end(); it != ite; ++it)
        {
            auto it1 = it(i2), ite2 = it1.end();
            auto it2 = adjacent_find(it1, ite2, [](int a, int b) {return a==1 && b==0;});
            auto it3 = adjacent_find(it2, ite2, [](int a, int b) {return a==0 && b==1;});
            if(it2 && it3 && it2.distance(it3) == count(it2, it3.next(), 0))
            {
                fill(it2, it3.next(), 1);
                ++cnt;
            }
        }
        return cnt;
    }
    
    void apply(Board &b)
    {
        int cnt;
        do
        {
            cnt = 0;
            cnt += applyone(b, mp(0, 0), DN, RT);
            cnt += applyone(b, mp(0, 0), RT, DN);
            cnt += applyone(b, mp(0, 7), LT, SW);
            cnt += applyone(b, mp(1, 7), DN, SW);
            cnt += applyone(b, mp(0, 0), RT, SE);
            cnt += applyone(b, mp(1, 0), DN, SE);
        }
        while(cnt);
    }
    
    int bestMove(vector<string> red, vector<string> blk, string who)
    {
        FOR(i, 8) board.pb(vector<int>(8, -1));
        
        int w = (who == "Red" ? 1 : 0);
        for(const auto &s:red) board[s[0]-'A'][s[1]-'1'] = w;
        for(const auto &s:blk) board[s[0]-'A'][s[1]-'1'] = w^1;
        
        int maxcnt = doCount(board);
        FOR(i, 8) FOR(j, 8)
        {
            if(board[i][j] < 0)
            {
                Board temp = board;
                temp[i][j] = 1;
                apply(temp);
                maxcnt = max(maxcnt, doCount(temp));
            }
        }
        
        return maxcnt;
    }
};