[白俊13460]仙丹を脱出する2
11308 ワード
A.方法
転がり玉は重力で玉を片側に集中させる現象である.従って、左壁の関数と矩形板をそれぞれ90度、180度、270度回転させる関数を実現する.
上記の関数を実現し,DFSおよびすべての状況に対して4方向に傾斜するすべての方向を探索しようとした.このとき、テストボックスだけを回すのにも時間がかかりました.この方法は誤りであり,10回以下の方向があってもDFSで実現すれば最悪の場合には約4^10の探索が行われるからである.また,同じ場合の矩形板を既に目撃していれば,その板の探索には意味がない.
B.実施
vector
矩形板の球の関数を左に移動します.
1-1. '#', '.', '0は変更されません.
1-2. ビーズを発見した場合、スペースのほかに、詰まった場所を見つけて挿入します.
1-3. ブラウズ中に穴が見つかったときの成功と失敗を確認します.
void solver(int cnt)
BFSによる解凍
[input]int cnt:何回傾いたか
3-1:BFS用に用意されたキューから状況の数を取得する.
3-2:マザーボードが以前に使用された状態であることを確認します.
3-3:初めて見たボードの場合は、上の1番と2番の関数を使用して、条件に合っているかどうかをナビゲートします.
3-4:次のソルバ関数でポップアップされたキューをリフレッシュする回数
C.コード
#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;
int T;
int N, M;
int i, j;
vector<vector<char>> t;
int answer = 0;
queue<vector<vector<char>>> q;
int qs;
vector<vector<int>> point;
vector<vector<char>> moveLeft(vector<vector<char>>& v) {
vector<vector<char>> ret;
int goal = 0;
int i, j, k;
for(i = 0; i < v.size(); i++) {
vector<char> tv;
tv.clear();
for(j = 0; j < v[i].size(); j++) {
//1-1
if(v[i][j] == '#' || v[i][j] == '.' || v[i][j] == 'O') {
tv.push_back(v[i][j]);
}
// red or blue
else {
for(k = tv.size() - 1; k >= 0; k--) {
//1-2
if(tv[k] == '#' || tv[k] == 'B' || tv[k] == 'R' || tv[k] == 'O') {
//1-3
if(tv[k] == 'O') {
if(v[i][j] == 'R') {
if(goal == 0)
goal = 1;
}
else {
goal = -1;
}
}
break;
}
}
if(goal == 0)
tv.insert(tv.begin() + k + 1, v[i][j]);
}
}
ret.push_back(tv);
}
if(goal != 0) {
ret.clear();
ret.resize(1);
if(goal == -1) {
ret[0].push_back('X');
}
else {
ret[0].push_back('O');
}
}
return ret;
}
vector<vector<char>> rotateOne(vector<vector<char>>& t) {
vector<vector<char>> ret;
ret.resize(t[0].size());
for(int i = 0; i < ret.size(); i++) {
for(int j = 0; j < t.size(); j++) {
ret[i].push_back(t[j][t[0].size() - i - 1]);
}
}
return ret;
}
vector<vector<char>> rotateTwo(vector<vector<char>>& t) {
vector<vector<char>> ret;
ret.resize(t.size());
for(int i = 0; i < ret.size(); i++) {
for(int j = 0; j < t[0].size(); j++) {
ret[i].push_back(t[t.size() - i - 1][t[0].size() - j - 1]);
}
}
return ret;
}
vector<vector<char>> rotateThree(vector<vector<char>>& t) {
vector<vector<char>> ret;
ret.resize(t[0].size());
for(int i = 0; i < ret.size(); i++) {
for(int j = 0; j < t.size(); j++) {
ret[i].push_back(t[t.size() - j - 1][i]);
}
}
return ret;
}
void solver(int cnt) {
if(cnt > 10)
return;
int into = 0;
for(int x = 0; x < qs; x++) {
//3-1
vector<vector<char>> vt = q.front();
q.pop();
int stop = 0;
vector<int> pv(4, 0);
//3-2
for(int i = 0; i < vt.size();i++) {
for(int j = 0; j < vt[0].size();j++) {
if(vt[i][j] == 'R') {
pv[0] = i;
pv[1] = j;
}
else if(vt[i][j] == 'B') {
pv[2] = i;
pv[3] = j;
}
}//cout << endl;
}
for(int i = 0; i < point.size(); i++) {
if(point[i][0] == pv[0] && point[i][1] == pv[1] && point[i][2] == pv[2] && point[i][3] == pv[3]) {
stop = 1;
}
}
//3-3
if(stop == 0)
{
point.push_back(pv);
vector<vector<char>> tv1 = moveLeft(vt);
if(tv1.size() == 1) {
if(tv1[0][0] == 'O') {
answer = cnt;
into = 1;
}
}
else {
q.push(tv1);
}
vector<vector<char>> tv2_1 = rotateOne(vt);
vector<vector<char>> tv2 = moveLeft(tv2_1);
if(tv2.size() == 1) {
if(tv2[0][0] == 'O') {
answer = cnt;
into = 1;
}
}
else {
tv2 = rotateThree(tv2);
q.push(tv2);
}
vector<vector<char>> tv3_1 = rotateTwo(vt);
vector<vector<char>> tv3 = moveLeft(tv3_1);
if(tv3.size() == 1) {
if(tv3[0][0] == 'O') {
answer = cnt;
into = 1;
}
}
else {
tv3 = rotateTwo(tv3);
q.push(tv3);
}
vector<vector<char>> tv4_1 = rotateThree(vt);
vector<vector<char>> tv4 = moveLeft(tv4_1);
if(tv4.size() == 1) {
if(tv4[0][0] == 'O') {
answer = cnt;
into = 1;
}
}
else {
tv4 = rotateOne(tv4);
q.push(tv4);
}
}
}
if(into == 1)
return;
//3-4
qs = q.size();
solver(cnt + 1);
}
int main() {
//scanf("%d", &T);
T = 1;
for(int tc = 0; tc < T; tc++) {
t.clear();
answer = -1;
while(!q.empty()) {
q.pop();
}
point.clear();
scanf("%d %d", &N, &M);
t.resize(N);
for(i = 0; i < N; i++) {
for(j = 0; j < M; j++) {
char tmp;
//scanf("%c ", &tmp);
cin >> tmp;
t[i].push_back(tmp);
}
}
q.push(t);
qs = q.size();
solver(1);
printf("%d\n", answer);
}
return 0;
}D.結果
Reference
この問題について([白俊13460]仙丹を脱出する2), 我々は、より多くの情報をここで見つけました https://velog.io/@pamrk2002/백준-13460구슬-탈출-2テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol