SRM509 Div2 Hard(1000) NumberLabyrinthDiv2

NumberLabyrinthDiv2

ある空のセルを２回通る動きが最善になることはないので、高々K回空のセルを通りその時は好きな距離を飛べると考えても答えは同じ。スタート地点からそれぞれの地点にあとk回飛べる状態でたどり着く最短手数を幅優先探索で求める。

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

class NumberLabyrinthDiv2{public:
int getMinimumNumberOfMoves( vector <string> board, int r1, int c1, int r2, int c2, int K )
{
    int dx[] = { 0, 1, 0, -1 };
    int dy[] = { 1, 0, -1, 0 };

    int R = (int)board.size();
    int C = (int)board[0].size();
    int INF = R*C;
    
    vector<vector<vector<int> > > D( R, vector<vector<int> >( C, vector<int>( K+1, INF ) ) );
    D[r1][c1][K] = 0;

    for ( int d=0; ; d++ )
    {
        bool up = false;
        for ( int y=0; y<R; y++ )
        for ( int x=0; x<C; x++ )
        for ( int k=0; k<=K; k++ )
        if ( D[y][x][k] == d )
            for ( int i=0; i<4; i++ )
            {
                if ( board[y][x] != '.' )
                {
                    int l = board[y][x] - '0';
                    int tx = x + l*dx[i];
                    int ty = y + l*dy[i];
                    if ( 0<=tx && tx<C && 0<=ty && ty<R && D[ty][tx][k]==INF )
                        D[ty][tx][k] = D[y][x][k] + 1,  up = true;
                }

                if ( board[y][x] == '.'  &&  k>0 )
                for ( int l=1; l<=9; l++ )
                {
                    int tx = x + l*dx[i];
                    int ty = y + l*dy[i];
                    if ( 0<=tx && tx<C && 0<=ty && ty<R && D[ty][tx][k-1]==INF )
                        D[ty][tx][k-1] = D[y][x][k] + 1,  up = true;
                }
            }

        if ( ! up )
            break;
    }

    int ans = *min_element( D[r2][c2].begin(), D[r2][c2].end() );
    return ans<INF ? ans : -1;
}};