結果
| 問題 | No.585 工夫のないパズル |
| ユーザー |
 manugino
|
| 提出日時 | 2017-11-05 22:48:02 |
| 言語 | C++11 (gcc 11.4.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| コード長 | 19,782 bytes |
| コンパイル時間 | 1,029 ms |
| コンパイル使用メモリ | 100,532 KB |
| 実行使用メモリ | 5,248 KB |
| 最終ジャッジ日時 | 2024-11-24 02:56:46 |
| 合計ジャッジ時間 | 1,721 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
5,248 KB |
| testcase_01 | AC | 1 ms
5,248 KB |
| testcase_02 | AC | 2 ms
5,248 KB |
| testcase_03 | AC | 2 ms
5,248 KB |
| testcase_04 | AC | 2 ms
5,248 KB |
| testcase_05 | AC | 2 ms
5,248 KB |
| testcase_06 | AC | 2 ms
5,248 KB |
| testcase_07 | AC | 2 ms
5,248 KB |
| testcase_08 | AC | 1 ms
5,248 KB |
| testcase_09 | AC | 2 ms
5,248 KB |
| testcase_10 | AC | 1 ms
5,248 KB |
| testcase_11 | AC | 2 ms
5,248 KB |
| testcase_12 | AC | 1 ms
5,248 KB |
| testcase_13 | AC | 2 ms
5,248 KB |
| testcase_14 | AC | 1 ms
5,248 KB |
ソースコード
//#define debug //*******************************************************************************************************************************************
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// [Tips]
// XCodeでのEOF入力はCtrl+D
// ¥はAlt+\
// ansは結構INTの範囲2,147,483,647を超えることがあるのでlong long使っておいたほうが良い
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////
//yukicorder
//No.585 工夫のないパズル
//
//IDA*探索に挑戦したいが、まずは愚直に、昔8パズルでやったのを思い出して
//1. なにも考えず幅優先探索BFS
//結果：当然のごとくTLE・・・
//
//そういえば8パズルでは双方向探索で劇的に速くなったけど・・・
//2. せっかくだから双方向BFSまた実装してみるか、復習がてら。どうせTLEになるだろうとは思いつつ
//結果：それでも変わらず同じ問題でTLE・・・無駄な労力返せ〜
//
//ということでようやく本題のIDA*探索へ。大いに蟻本と渦巻本を参考にしながら
//3. 知識あり(ヒューリスティクスを使った) ID-DFS (Iterative Deepening Depth-First Search) である、ID-A*を実装
//結果：なんとダメでした。TLE。2のときより1問しか多く解けなかった。
//もっとフツーに攻略法ライクに解くんだってさ。これまた徒労でした。ちーん。。。
//
//3-a. 構造体PUZZLEの状態をstring stateで表現していたが、これを試しにchar配列にしてみると高速化されたりしないか実験
//なんとこれだけで大幅にACが増えた！！string使ってたのバカバカバカバカバカバカ！！
//86手の問題が解けて、96手の問題がTLEだったから、あとほんの少し高速化できればいけそうなんだけどなー。
//
//実例：
//まず以下が3.の状態でstringを使っている場合、
//FHLE
//MOIC
//DNPB
//AKGJ
//20
//R 0 2
//R 2 1
//R 3 1
//C 1 1
//R 2 1
//C 0 1
//R 3 3
//C 0 1
//R 0 3
//R 1 2
//R 2 2
//C 2 1
//R 1 1
//C 1 1
//R 2 2
//C 2 3
//R 2 1
//R 0 1
//C 2 2
//R 0 3
//numOfSearch = 318372
//0.0960 sec
//Program ended with exit code: 0
//
//そして以下がstateをchar配列に変えた場合であるが、めちゃめちゃ速くなった!!! 0.0960sec ===> 0.0300sec
//こういう構造体を自作するケースでstring使っちゃうとめっちゃ遅くなるんやなって実感できてたいへん勉強になりました。
//FHLE
//MOIC
//DNPB
//AKGJ
//20
//R 0 2
//R 2 1
//R 3 1
//C 1 1
//R 2 1
//C 0 1
//R 3 3
//C 0 1
//R 0 3
//R 1 2
//R 2 2
//C 2 1
//R 1 1
//C 1 1
//R 2 2
//C 2 3
//R 2 1
//R 0 1
//C 2 2
//R 0 3
//numOfSearch = 318372
//0.0300 sec
//Program ended with exit code: 0
//
//
//
//
//まだ意地でもad−hocのやり方やらずに、なんとか教科書解法で解こうとしている・・・ので、
//4. 知識あり(ヒューリティクスを使った) BFS (Breadth-First Search) である、A*を試しに実装してみる <== イマココ
//結果：全然TLE。サンプル問題3題くらいしかACならず。やっぱり優先順位比較とかする分めちゃめちゃ遅くなるんだなあ・・・。
//ただ、先の例で見ると以下の通り、実行速度はめちゃめちゃ遅いけど、探索回数自体はめちゃめちゃ減っているという。トレードオフやなあ。
//当然のごとく、最短手数は得られなくなっている。じゃあもうA*探索ってメリットなくない？って思っちゃう。
//FHLE
//MOIC
//DNPB
//AKGJ
//18
//R 0 1
//C 0 1
//R 3 1
//C 1 1
//C 3 1
//R 2 1
//C 3 1
//C 0 2
//R 1 2
//C 2 1
//R 0 2
//C 0 1
//R 1 1
//R 2 3
//C 0 1
//C 1 1
//R 2 1
//C 1 3
//numOfSearch = 43269
//2.2190 sec
//Program ended with exit code: 0
//
//
//ということでここまで徒労した上で、ようやく本解答に挑戦
//5. Ad-hocなこのパズルの必勝法を実装 <== イマココ
//
////////////////////////////////////////
#ifdef debug
#include <chrono>
#endif
#include <iostream>
#include <algorithm> // next_permutation
#include <iomanip>
#include <cmath>
#include <vector>
#include <sstream>
#include <string>
#include <cstring> //memcpy
#include <cstdio>
#include <stack>
#include <queue>
#include <list>
#include <numeric> //accumulate
#include <map>
//#include <unordered_map> //hash func.
#include <fstream> //ifstream, ofstream
#include <iterator> //insert_iterator::inserter
#include <set>
//#define NDEBUG //If NDEBUG is defined before #include <cassert>, assert will be ignored. You had better define NDEBUG when u submit the code.
#include <cassert> //assert
using namespace std;
#define dout cout
//If u wanna output to a text file instead of standard output, plz define OUTPUTFILE.
//#define OUTPUTFILE "output.txt" //************************************************************
#ifdef OUTPUTFILE
#define dout outputfile
ofstream outputfile(OUTPUTFILE);
#define OutputFilePath "/Users/Nag/Documents/Prgm/Test/DerivedData/Test/Build/Products/Debug/output.txt"
#endif
#define din cin
//If u wanna input from a text file instead of standard input, plz define INPUTFROMTEXTFILEを.
//#define INPUTFILE "input.txt" //**************************************************************
#ifdef INPUTFILE
#define din inputfile
ifstream inputfile(INPUTFILE);
#endif
#define scand(A) scanf("%d", &(A))
#define scans(A) scanf("%s", (A))
#define printd(A) printf("%d\n", (A))
#define prints(A) printf("%s\n", (A))
#define disp(A) dout << #A << " = " << setw(3) << (A) << endl
#define disP(A) dout << setw(3) << (A) << " "
#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define show(A,s,g) dout << #A << " = "; rep(j, (s), (g)) {disP(A[j]);} dout << endl
#define showi(A,s,g) dout << #A << " = "; rep(j, (s), (g)) {disP(j);} dout << endl
#define line dout << "---------------\n"
#define sign(x) ((x)>0)-((x)<0) //x<0: -1, x=0: 0, x>0: +1
#define p(i) ((i)/2)
#define l(i) ((i)*2)
#define r(i) ((i)*2+1)
#define sibling(i) (i^1) //the other sibling of i (ex. 16^1 = 17, 17^1 = 16)
#define isRightChild(i) (i&1) // ex. 16&1 = 0, 17&1 = 1
#define isLeftChild(i) (!(i&1)) // ex. 16&1 = 1, 17&1 = 0
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef vector<int> vi;
typedef long long ll;
typedef unsigned long long ull;
//const int INF = (1LL<<31)-1;
const int NONE = -1;
//const ll INF_LL = (ll)9e18-1LL; //Be careful for overflow.
//const ull INF_ULL = (ull)1e19-1ULL;
//#define MOD 1000000007 //大きい素数の代表といえばこの人、10億7さん
#define N_MAX 100010 //num of vertex or element
//#define M_MAX 124760 //num of edge
//#define DATA_MAX 1010
#define N 4
#define N2 16
char GOAL[N2+1] = "ABCDEFGHIJKLMNOP";
//24 patterns of possible move
#define K_MAX 24
char dir[K_MAX] = {'R','R','R','R','R','R','R','R','R','R','R','R','C','C','C','C','C','C','C','C','C','C','C','C'}; //direction
int pos[K_MAX] = { 0 , 0 , 0 , 1 , 1 , 1 , 2 , 2 , 2 , 3 , 3 , 3 , 0 , 0 , 0 , 1 , 1 , 1 , 2 , 2 , 2 , 3 , 3 , 3 }; //position
int dif[K_MAX] = { 1 , 2 , 3 , 1 , 2 , 3 , 1 , 2 , 3 , 1 , 2 , 3 , 1 , 2 , 3 , 1 , 2 , 3 , 1 , 2 , 3 , 1 , 2 , 3 }; //difference
int target_i;
int target_j;
#define round(i) (((i)%N+N)%N) //0, 1, ... , N-1に変換する (負の数も含めて)
struct PUZZLE {
char state[N2+1];
vi path; //初期状態からここまでの手
int cost; //初期状態からここまでの手数、pathに保存されている手の数に等しい
bool isGoal() {
return not strcmp(this->state, GOAL);
}
void display() {
#ifdef debug
dout << "----\n";
disp(this->state);
show(path,0,this->cost);
disp(this->cost);
rep(i,0,N) {
rep(j,0,N) {
dout << (i==target_i and j== target_j ? "*" : " ") << this->state[i*N+j] << " ";
}
dout << endl;
}
dout << endl;
#endif
}
void rotate(int k) { //pをk番目 (k=0...23) の動かし方で1手動かして返す
//同時に、cost、pathも更新する
#ifdef debug
dout << "--- rotate( " << k << " )\n";
disp(dir[k]);
disp(pos[k]);
disp(dif[k]);
#endif
path.push_back(k);
this->cost++;
int start, last, jump;
char tmp[N2];
if(dir[k]=='R') {
jump = 1;
start = N * pos[k];
last = start + (N-1)*jump; // = start + 3
}
else {
assert(dir[k]=='C');
jump = N;
start = pos[k];
last = start + (N-1)*jump; // = start + 12
}
//一旦tmpにdifだけずらしてコピーしておいて
for(int i=start; i<=last; i+=jump) {
int next = i + dif[k] * jump;
if(next > last) next = i - (N - dif[k])*jump;
tmp[next] = state[i];
}
//元の配列を更新する
for(int i=start; i<=last; i+=jump) {
state[i] = tmp[i];
}
}
void rotRowToRight(int pos, int dif) {
int dir = 0;
rotate( dir*N*(N-1) + pos*(N-1) + dif-1 );
}
void rotColumnToDown(int pos, int dif) {
int dir = 1;
rotate( dir*N*(N-1) + pos*(N-1) + dif-1 );
}
void swap2AdjacentElementsInTheSameRow(int row, int j1, int j2) {
#ifdef debug
dout << "---- swap( row=" << row << ", " << j1 << ", " << j2 <<" )\n";
#endif
assert(0<=row and row<N);
assert(0<=j1 and j1<N);
assert(0<=j2 and j2<N);
assert(j1!=j2);
if(j1>j2) swap(j1, j2);
int column = round(j1 - 1);
assert(column!=j2);
#ifdef debug
disp(row);
disp(j1);
disp(j2);
disp(column);
#endif
rotColumnToDown(column, 1);
display();
rotRowToRight(row, 3);
display();
rotColumnToDown(column, 3);
display();
rotRowToRight(row, 2);
display();
rotColumnToDown(column, 1);
display();
rotRowToRight(row, 3);
display();
rotColumnToDown(column, 3);
display();
rotRowToRight(row, 3);
display();
}
} puzzle;
void init() {
}
void display() {
#ifdef debug
dout << "----\n";
#endif
}
void solve() {
#ifdef debug
dout << "======================== solve()\n";
puzzle.display();
#endif
int sorted_i = -1; //sorted_i行目の
int sorted_j = -1; //sorted_j番目のマスまでが揃えられている
int goal_i;
int goal_j;
//最下行を犠牲にして、それ以外のマスを揃える
rep(i,0,N*(N-1)) {
//i(targetChar)を揃える (i=0:A, i=1:B, ..., i=11:L)
//注意：この時点で、i-1まではすでに揃えられている状態
// その事実はsorted_i, sorted_jで表現することにする
char targetChar = i + 'A';
int targetPos = NONE;
//find targetChar
rep(j,0,N2) {
if( puzzle.state[j] == targetChar ) {
targetPos = j;
}
}
assert(targetPos!=NONE);
target_i = targetPos/N;
target_j = targetPos%N;
goal_i = i/N;
goal_j = i%N;
#ifdef debug
dout << "Step 0\n";
dout << "すでに対象が正しい位置に配置されている場合は、continue\n";
#endif
if( target_i == goal_i and target_j == goal_j ) {
//次の対象へ
sorted_j = round(sorted_j+1);
if(sorted_j==0) {
sorted_i++;
}
continue;
}
#ifdef debug
dout << "------------------------------\n";
disp(i);
disp(targetChar);
disp(targetPos);
disp(target_i);
disp(target_j);
disp(goal_i);
disp(goal_j);
disp(sorted_i);
disp(sorted_j);
puzzle.display();
#endif
int step1_j = NONE;
#ifdef debug
dout << "Step 1\n";
dout << "対象がフリーの行になければ、対象をフリーの行まで下げる\n";
#endif
if( target_i <= sorted_i ) {
step1_j = target_j;
puzzle.rotColumnToDown(target_j, 1);
target_i++;
assert(target_i<N);
puzzle.display();
}
#ifdef debug
dout << "Step 2\n";
dout << "列が揃っていれば、対象を右にずらす\n";
dout << "ただし、DまではStep 2をskipする\n";
#endif
if( targetChar>'D' and target_j == goal_j ) {
puzzle.rotRowToRight(target_i, 1);
target_j++;
target_j %= N;
puzzle.display();
}
#ifdef debug
dout << "Step 3\n";
dout << "goalマスと対象の行が違ったら、goalマスを対象と同じ行に下げる\n";
dout << "ただし、Dまでは、Step 3をskipする\n";
#endif
if( targetChar>'D' and goal_i != target_i ) {
assert(target_i > goal_i);
puzzle.rotColumnToDown(goal_j, target_i - goal_i);
puzzle.display();
}
#ifdef debug
dout << "Step 4\n";
dout << "goalマスと対象の列が違ったら、goalマスと同じ列に横にずらす\n";
#endif
if( target_j != goal_j ) {
puzzle.rotRowToRight(target_i, round(goal_j-target_j));
target_j = goal_j;
puzzle.display();
}
#ifdef debug
dout << "Step 5 (Step 3の逆手順)\n";
dout << "goalマスと対象の行が違ったら、goalマスの位置まで上げる\n";
#endif
if( goal_i != target_i ) {
puzzle.rotColumnToDown(target_j, round(goal_i-target_i));
target_i = goal_i;
puzzle.display();
}
#ifdef debug
dout << "Step 6\n";
dout << "Step 1を実行していた場合、つまり対象がフリーの行になく対象をフリーの行まで下げていた場合は、その分を戻す\n";
#endif
if( step1_j!=NONE ) {
puzzle.rotColumnToDown(step1_j, round(-1));
puzzle.display();
}
//次の対象へ
sorted_j = round(sorted_j+1);
if(sorted_j==0) {
sorted_i++;
}
}
#ifdef debug
dout << "Step M\n";
dout << "最下行の最左の要素 (M) が揃っていなければ、それを1手で揃える\n";
#endif
goal_i = N-1;
goal_j = 0;
char targetChar = goal_i*N + goal_j + 'A';
target_i = N-1;
target_j = NONE;
rep(j,0,N) {
if(puzzle.state[target_i*N + j] == targetChar) {
target_j = j;
break;
}
}
assert(target_j!=NONE);
if(goal_j!=target_j) {
puzzle.rotRowToRight(target_i, round(goal_j-target_j));
target_i = goal_i;
target_j = goal_j;
puzzle.display();
}
#ifdef debug
dout << "Step FINAL\n";
dout << "残り(N-1)要素を、ネットで見つけた「隣接する2マスを交換する手順」を使って、揃える\n";
#endif
goal_i = N-1;
goal_j = 1;
targetChar = goal_i*N + goal_j + 'A';
target_i = N-1;
target_j = NONE;
rep(j,0,N) {
if(puzzle.state[target_i*N + j] == targetChar) {
target_j = j;
break;
}
}
assert(target_j!=NONE);
#ifdef debug
disp(goal_j);
disp(target_j);
#endif
if(goal_j!=target_j) { //1文字目が揃っていない
#ifdef debug
dout << "Nが揃っていない\n";
#endif
if(target_j==2) { //今注目している文字 (1文字目に配置するべき文字) の位置が2
#ifdef debug
dout << "Nが2の位置にあるので、1,2をswapする\n";
#endif
puzzle.swap2AdjacentElementsInTheSameRow(target_i, 1, 2);
}
else { //今注目している文字 (1文字目に配置するべき文字) の位置が3
assert(target_j==3);
#ifdef debug
dout << "Nが3の位置にあるので、2,3をswap後、1,2をswap\n";
#endif
puzzle.swap2AdjacentElementsInTheSameRow(target_i, 2, 3);
puzzle.swap2AdjacentElementsInTheSameRow(target_i, 1, 2);
}
//1文字目が揃った!!
}
#ifdef debug
dout << "Nまで揃った\n";
#endif
//2文字目をチェック
target_j = 2;
targetChar = target_i*N + target_j + 'A';
if(puzzle.state[target_i*N + target_j]==targetChar) { //2文字目も揃っている、それすなわち3文字目も揃っている、つまり全部揃っている
return;
} else { //2文字目と3文字目が揃っていないのでswap
puzzle.swap2AdjacentElementsInTheSameRow(target_i, target_j, round(target_j+1));
}
#ifdef debug
dout << "すべて揃った\n";
#endif
assert(puzzle.isGoal());
}
int main() {
//cin, coutの高速化 ＊注意：cinを使うなら全部cinで、scanfを使うなら全部scanfで統一するように！
cin.tie(0); //cinとcoutの同期を切る
ios::sync_with_stdio(false); //iostreamとstdioの同期を切る
//read input data
// scand(N);
string s;
char ss[N2+1];
rep(i,0,N) {
din >> s;
rep(j,0,N) {
ss[i*N+j] = s[j];
}
}
ss[N2] = '\0';
//------------------------------------------------------------------------------------------
#ifdef debug
//start timer
auto startTime = chrono::system_clock::now();
#endif
//------------------------------------------------------------------------------------------
strcpy(puzzle.state, ss);
init();
display();
solve();
#ifdef debug
dout << "=== OUTPUT ===\n";
#endif
if( puzzle.cost!=NONE ) {
dout << puzzle.cost << endl;
rep(i,0,puzzle.cost) {
dout << dir[puzzle.path[i]] << " " << pos[puzzle.path[i]] << " " << dif[puzzle.path[i]] << endl;
}
}
else {
dout << "UNSOLVABLE!!!\n";
}
//------------------------------------------------------------------------------------------
#ifdef debug
//stop timer
auto endTime = chrono::system_clock::now();
auto dur = endTime - startTime;
auto msec = chrono::duration_cast<chrono::milliseconds>(dur).count();
dout << fixed << setprecision(4) << (double)msec/1000 << " sec \n";
#endif
//------------------------------------------------------------------------------------------
#ifdef INPUTFILE
inputfile.close();
#endif
#ifdef OUTPUTFILE
outputfile.close();
cout << "\"" << OutputFilePath << "\"" << endl;
#endif
return 0;
}