SRM563 Div2 Medium(550) CoinsGameEasy

CoinsGameEasy

全探索。

#include <string>
#include <vector>
using namespace std;

vector<string> B;
int w, h;

int BT( int d, int cx1, int cy1, int cx2, int cy2 )
{
    bool in1 = 0<=cx1 && cx1<w && 0<=cy1 && cy1<h;
    bool in2 = 0<=cx2 && cx2<w && 0<=cy2 && cy2<h;
    if ( !in1 && in2 || in1 && !in2 )
        return d;
    if ( !in1 && !in2 || d>10 )
        return 9999;

    int r = 9999;
    int dx[] = { 1, -1, 0, 0 };
    int dy[] = { 0, 0, 1, -1 };
    for ( int i=0; i<4; i++ )
    {
        int tx1 = cx1 + dx[i];
        int ty1 = cy1 + dy[i];
        int tx2 = cx2 + dx[i];
        int ty2 = cy2 + dy[i];
        if ( 0<=tx1 && tx1<w && 0<=ty1 && ty1<h && B[ty1][tx1]=='#' )
            tx1 = cx1,  ty1 = cy1;
        if ( 0<=tx2 && tx2<w && 0<=ty2 && ty2<h && B[ty2][tx2]=='#' )
            tx2 = cx2,  ty2 = cy2;
        r = min( r, BT(d+1,tx1,ty1,tx2,ty2) );
    }

    return r;
}

class CoinsGameEasy{public:
int minimalSteps( vector <string> board )
{
    ::B = board;
    w = (int)board[0].size();
    h = (int)board.size();

    int cx1=-1, cy1, cx2, cy2;
    for ( int y=0; y<h; y++ )
    for ( int x=0; x<w; x++ )
    if ( board[y][x]=='o' )
    {
        if ( cx1==-1 )
            cx1 = x,  cy1 = y;
        else
            cx2 = x,  cy2 = y;
    }

    int ans = BT( 0, cx1, cy1, cx2, cy2 );
    return ans<=10 ? ans : -1;  
}};