SRM563 Div2 Medium(550) 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; }};