結果
| 問題 |
No.585 工夫のないパズル
|
| コンテスト | |
| ユーザー |
 manugino
|
| 提出日時 | 2017-11-01 23:25:09 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 10,365 bytes |
| コンパイル時間 | 1,355 ms |
| コンパイル使用メモリ | 110,128 KB |
| 実行使用メモリ | 562,988 KB |
| 最終ジャッジ日時 | 2024-11-22 14:49:48 |
| 合計ジャッジ時間 | 36,218 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 TLE * 1 |
| other | WA * 3 TLE * 8 MLE * 1 |
ソースコード
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// [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になるだろうとは思いつつ <== イマココ
//
////////////////////////////////////////
//#define debug //*******************************************************************************************************************************************
#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 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 ll INF_LL = (ll)9e18-1LL; //Be careful for overflow.
const ull INF_ULL = (ull)1e19-1ULL;
const int NONE = -1;
const ll MOD = (ll)1e9+7; //大きい素数の代表といえばこの人、10億7さん
const int N_MAX = 3010; //num of vertex or element
const int M_MAX = 124760; //num of edge
const int DATA_MAX = 1010;
int N = 4;
int N2 = N*N;
string GOAL = "ABCDEFGHIJKLMNOP";
//24 patterns of possible move
const int 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
//search direction
const int FORWARD = 1;
const int REVERSE = -1;
int ans = 0;
struct PUZZLE {
string state;
string path;
int direction; //1: forward search direction, -1: reverse search direction
bool operator < (const PUZZLE &p) const { //for map<PUZZLE, bool>
rep(i,0,N2) {
if(state[i]==p.state[i]) continue;
else return this->state[i] < p.state[i];
}
return false; //completely equal
}
bool isGoal() {
return this->state==GOAL;
}
void display() {
dout << "----\n";
disp(this->state);
disp(this->path);
disp(this->direction);
rep(i,0,N) {
rep(j,0,N) {
dout << this->state[i*N+j];
}
dout << endl;
}
dout << endl;
}
static PUZZLE rotate(PUZZLE p, int k) { //pをk番目 (k=0...23) の動かし方で1手動かして返す
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] = p.state[i];
}
//元の配列を更新する
for(int i=start; i<=last; i+=jump) {
p.state[i] = tmp[i];
}
return p;
}
};
void init() {
}
void display() {
#ifdef debug
dout << "----\n";
#endif
}
string solve_BFS(PUZZLE p) {
queue<PUZZLE> Q;
map<PUZZLE, pair<int, string> > alreadySearched; //int = search direction
p.path = "";
p.direction = FORWARD;
alreadySearched[p] = make_pair(p.direction, "");
Q.push(p);
PUZZLE g;
g.state = GOAL;
g.path = "";
g.direction = REVERSE;
alreadySearched[g] = make_pair(g.direction, "");
Q.push(g);
PUZZLE x, y;
while(not Q.empty()) {
x = Q.front(); Q.pop();
#ifdef debug
dout << "=====================\n";
x.display();
#endif
//check if solved or not
if(alreadySearched[x].first * x.direction < 0) {
#ifdef debug
dout << "GOAAAAAAAAAAAAAAAAAAAL!!\n";
#endif
//construct actual solution move from both 2 pathes
string path1, path2;
if(x.direction>0) {
path1 = x.path;
path2 = alreadySearched[x].second;
} else {
path2 = x.path;
path1 = alreadySearched[x].second;
}
//prosess path2
string path3 = "";
for(int i=0; i<path2.size(); i+=3) {
if(path2[i+2]=='1') path2[i] = '3';
if(path2[i+2]=='3') path2[i] = '1';
path3.insert(path3.begin(), path2[i+2]);
path3.insert(path3.begin(), path2[i+1]);
path3.insert(path3.begin(), path2[i]);
}
return path1 + path3;
}
//xから1手で遷移できる状態yをすべて羅列する
rep(k,0,K_MAX) {
y = x.rotate(x, k);
#ifdef debug
dout << "---\n";
disp(k);
y.display();
#endif
if( not alreadySearched[y].first or (alreadySearched[y].first * y.direction < 0) ) {
alreadySearched[y].first = y.direction;
y.path += dir[k];
y.path += to_string(pos[k]);
y.path += to_string(dif[k]);
alreadySearched[y].second = y.path;
Q.push(y);
#ifdef debug
dout << "since y has not been searched yet, add into Q.\n";
disp(y.path);
#endif
}
}
}
return "UNSOLVABLE";
}
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, initialState;
rep(i,0,N) {
din >> s;
initialState += s;
}
PUZZLE puzzle;
puzzle.state = initialState;
init();
display();
//------------------------------------------------------------------------------------------
#ifdef debug
//start timer
auto startTime = chrono::system_clock::now();
#endif
//------------------------------------------------------------------------------------------
string sol = solve_BFS(puzzle);
#ifdef debug
dout << "=== OUTPUT ===\n";
#endif
dout << sol.size()/3 << endl;
rep(i,0,sol.size()) {
dout << sol[i] << (i%3==2? "\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;
}