問題はこちら
No.228 ゆきこちゃんの 15 パズル - yukicoder
今現在yukicoderの「解説」からリンクされてるやつは嘘解法なので注意
入れ替えを行うと動けなくなるので、入れ替えをするならそのパネルは移動後に正しい位置に移らならなければならない。
そういうわけで「空きマスと上下左右隣接するマスの内、『いま空きマスがいる位置に本来いるべきパネル』（これは高々1つ）があればそこと入れ替える」という操作を順にやっていき、最終的に動かせなくなった時にパズルが完成しているか確かめれば良い。
……これ実装するの大変そうじゃん？
ということでもう少し簡単な必要十分条件を考えた
・空きマスを、「いま空きマスがいる位置に本来いるべきパネル」と入れ替えていった時、最終的に正しい配置になる
・全てのパネルは本来いるべき位置にあるか、その上下左右に隣接している
1つ目の条件をさっきと比べると、空きマスの移動先を上下左右に限らなくなっている。つまり1つ目の条件だけでは、空きマスがワープすることも認めている。
（条件が緩くなっているのだから、これを満たさなければ答えはもちろんNOになる）
で、1つ目の条件が満たされた時、空きマスが実際にはワープしていないことの必要十分条件が2つ目の条件になる
ということでこれを実装する
都合上、与えられた数から1減じ、パネルを0～14、空きマスを-1とする
15パズルの位置を表す行/列は0-basedとする。
2次元配列にするとめんどくさいから1次元で読み込んでしまう。
「上下左右に隣接している」を「マンハッタン距離が1」と読み替える。
i番目に読み込んだ値(0-based)はfloor(i/4)行(i%4)列目のパネルであり、パネルjが本来いるべき位置はfloor(j/4)行(j%4)列目なので
正しい位置とのマンハッタン距離は|floor(i/4)-floor(j/4)|+|i%4-j%4|で与えられる
以上を使って実装
int main(){ int i,j,d,s=0,target,a[20]={}; for(i=0;i<16;i++){ scanf("%d",&j); a[i]=--j; //jは1減らしてから格納 if(j!=-1){ //空きマスでなければ d=abs(i/4-j/4)+abs(i%4-j%4); //距離を調べて if(d>1){puts("NO");return 0;} //正しい位置からの距離が2以上のものがあればダメ else if(d>0)s++; //正しい位置にないものの個数を数える } } target=-1; while(target!=15){ for(i=0;a[i]!=target;i++); //targetのパネルを探す s--; //tagetのパネルと空きマスを入れ替えたので、パネルが1つ正しい位置に戻った target=i; //空きマスはtargetのパネルがあるi番目のマスと入れ替えられるので //今度はこのマスに本来いるべきパネルを探す } puts(s==-1?"YES":"NO"); //実際には最初に空きマスの位置を探した分で余分に1回decしてしまっているので //全てのパネルが正しい位置に戻っていればsは-1になる return 0; }
これを短くしたい
まず後半の空きマスの変遷だが、これは逆にたどる。
空きマスがi番目の位置にやってくる直前は「i番目にいたパネルが本来いるべき位置」にいるはずであり、最終的にいる位置は15番目であることから、この部分は
for(i=15;i!=-1;i=a[i])s--;
とあっさり書くことができる
ところで最初の各パネルに対し「(正しい位置までの距離)+(正しい位置にいるなら0、さもなくば1)」という量を考えると
これは、正しい位置にいるパネルに対して0、距離n(>0)の位置にいるパネルに対しn+1を返すのでこれを利用すると前半と後半がまとめられ次のように書ける
s,i,a[17]; main(){ for(;~scanf("%d",a+i);i++)if(a[i]--)s+=abs(a[i]/4-i/4)+abs(a[i]%4-i%4)+(a[i]!=i); //全てのパネルが距離1以下にあるなら、sの値は2*(正しい位置にないパネルの数) //距離2以上のパネルがあればsはそれより大きくなる for(i=15;~i;i=a[i])s-=2; //sは2*(正しい位置に戻ったパネルの数+1)だけ小さくなった i=!puts(s+2?"No":"Yes"); //よって全てのパネルが距離1以下にあり、全てのパネルが正しい位置に戻ったなら //sは-2になっているはず（0といいたいところだがfor文が1回多い） }
後半のループの部分を
for(i=15;~i;i=a[i])s-=2; for(i=15;~(i=a[i]);)s-=2;
と書けば、最初の1回分がなくなるので、出力の分岐がs?…でよくなる
そのた細々をいつもどおり縮めて
s,i,a[17]; main(){ for(;~scanf("%d",a+i);i++)a[i]--?s+=abs(a[i]/4-i/4)+abs(a[i]%4-i%4)+(a[i]!=i):0; for(i--;~(i=a[i]);s-=2); i=!puts(s?"No":"Yes"); }
ここで後半をぐぐぐっと睨むと、カッコ外したいなあと思えてくるので頑張ると
s,i,a[17]; main(){ for(;~scanf("%d",a+i);i++)a[i]--?s+=abs(a[i]/4-i/4)+abs(a[i]%4-i%4)+(a[i]!=i):0; for(i=-i;i=~a[~i]?:!puts(s?"No":"Yes");s-=2); }
と1B短縮でき143B
5/19追記
ポインタを使うのを試してなかった
s,i,a[17];main(){for(;~scanf("%d",a+i);i++)a[i]--?s+=abs(a[i]/4-i/4)+abs(a[i]%4-i%4)+(a[i]!=i):0;for(i=-i;i=~a[~i]?:!puts(s?"No":"Yes");s-=2);} s,i,a[17],*p=a;main(){for(;~scanf("%d",p);p++,i++)~--*p?s+=abs(*p/4-i/4)+abs(*p%4-i%4)+(*p!=i):0;for(i=-i;i=~a[~i]?:!puts(s?"No":"Yes");s-=2);} //同じ長さか。pのincをまとめられないかな s,i,a[17],*p=a-1;main(){for(;~scanf("%d",++p);i++)~--*p?s+=abs(*p/4-i/4)+abs(*p%4-i%4)+(*p!=i):0;for(i=-i;i=~a[~i]?:!puts(s?"No":"Yes");s-=2);} //まてよ、iさえずれなければpでの読み込み先はずれててもいいのでは？ s,i,a[17],*p=a;main(){for(;~scanf("%d",++p);i++)*p?s+=abs(~-*p/4-i/4)+abs(~-*p%4-i%4)+(~-*p!=i):0;for(;i=a[i]?:!puts(s?"No":"Yes");s-=2);} //indexずれにより後半のループが単純になった s,i,a[17],*p=a;main(){for(;~scanf("%d",++p)?*p?s+=abs(~-*p/4-i/4)+abs(~-*p%4-i%4)+(~-*p!=i):0,++i:(s-=2,i=a[i]?:!puts(s+2?"No":"Yes")););} //for文圧縮をするも同じ長さ i,a[17],*p=a;main(s){for(;~scanf("%d",++p)?*p?s+=abs(~-*p/4-i/4)+abs(~-*p%4-i%4)+(~-*p!=i):0,++i:(s-=2,i=a[i]?:!puts(~s?"No":"Yes")););} //sの初期値を変えて2B短縮 i,a[17],*p=a;main(s){for(;i=~scanf("%d",++p)?*p?s+=abs(~-*p/4-i/4)+abs(~-*p%4-i%4)+(~-*p!=i):0,i+1:(s-=2,a[i]?:!puts(~s?"No":"Yes")););} //更にiの代入をくくりだして i,a[17],*p=a;main(s){for(;i=~scanf("%d",++p)?*p?s+=abs(~-*p/4-i/4)+abs(~-*p%4-i%4)+(~-*p!=i):0,i+1:a[i]?:!puts(s+31?"No":"Yes");)s-=2;} //s-=2を外に出してカッコを外し1B短縮
135B
