SRM454 Div2 500 WordsGame - kusano

行ごと列ごとの交換なので、他の行・列に文字を移すことはできない。例えば、↓の例で s と c は常に異なる行・列に含まれる。各行と列を独立に考えて目的の単語を作る最小手数を答える。

sdf
bca
hgf

貪欲に交換していっても最小手数が求まるのだが、なぜ貪欲で良いのかがわからなかった。EditorialやForumを読むと、正しい解法はこんな感じ。

各文字の位置から目的の位置まで矢印を引く。この矢印によってできる輪（巡回置換）は (輪の大きさ)-1 手で全ての文字を目的の位置に移動できる。それぞれの輪について１手省略できると考えると、最小手数は (文字列長)-(輪の個数)。

文字を目的の位置に移動する任意の交換は輪のサイズを１つ縮めるので、たしかに貪欲アルゴリズムでも最小手数が出てくる。

#include <string>
#include <vector>

using namespace std;

class WordsGame
{
public:
    int minimumSwaps( vector <string> grid, string word );
    int check( string from, string to );
};

int WordsGame::minimumSwaps( vector <string> grid, string word )
{
    int n = (int)grid.size();
    int m = n;

    for ( int i=0; i<n; i++ )
    {
        string row, col;

        for ( int j=0; j<n; j++ )
            row += grid[i][j],
            col += grid[j][i];

        m = min( m, check(row,word) );
        m = min( m, check(col,word) );
    }

    return m<n ? m : -1;
}

//  fromからtoへ書き換えるときの最小手数
//  不可能ならば文字列長を返す
int WordsGame::check( string from, string to )
{
    int n = (int)from.length();

    int c;
    for ( c=0; ; c++ )
    {
        //  未チェックの文字を探す
        int t;
        for ( t=0; t<n && from[t]=='_'; t++ )
            ;
        if ( t >= n )
            break;
        
        //  巡回置換に含まれる文字をチェック
        while ( from[t] != '_' )
        {
            int p = t;

            t = (int)to.find( from[t] );
            if ( t == string::npos )
                return n;

            from[p] = to[t] = '_';
        }
    }

    return n - c;
}