yukicoder 228 ゆきこちゃんの 15 パズル

2015/06/20 (Sat) yukicoder 貪欲

問題

問題文

方針

空いているマスの隣に，空いている場所にあるべきブロックがあれば，スライドしてそこに持ってくる． これを繰り返して，目的の配置にするか判定する． 各マスはただ $1$ 度だけ移動するかしないかのいずれかしかなく，また最終的に一致するかしないかの二者択一なので，移動すべきなら必ず移動しないといけない．

実装

signed main(){
    int T;
#ifdef LOCAL
    T = 3;
#else
    T = 1;
#endif
    rep(i,T){
        int g[4][4];
        int sj = -1, si = -1;
        rep(i,4)rep(j,4){
            cin >> g[i][j];
            if(g[i][j]==0) sj = j, si = i;
        }
        int di[] = {0,1,0,-1};
        int dj[] = {1,0,-1,0};
        while(1){
            bool ok = false;
            rep(d,4){
                int ni = si+di[d];
                int nj = sj+dj[d];
                if(ni < 0 || nj < 0 || ni >= 4 || nj >= 4) continue;
                int a = g[ni][nj];
                if(a == si*4+sj+1){
                    swap(g[si][sj],g[ni][nj]);
                    si = ni, sj = nj;
                    ok = true;
                    break;
                }
            }

            // rep(i,4){
            //     rep(j,4){
            //         cout << g[i][j] << " ";
            //     }
            //     cout << endl;
            // }

            if(ok) continue;
            else break;
        }
        bool ok = true;
        rep(i,4)rep(j,4){
            ok &= g[i][j] == i*4 + j+1 || (i==3 && j==3);
        }
        puts(ok ? "Yes" : "No");
    }
}