標準9012:DSLR

22487 ワード
BFS cpp テキストリンク
https://www.acmicpc.net/problem/9019

1.近接

  • 「最少」のコマンドを生成するため、最大値を求める必要がありますが、DFSはずっと掘る道なので、最大値、最低価格を求める問題とは程遠いです.
    =>必要な値が得られるとすぐに終了するBFSは、最大、最小に一致する経路探索方法である.
  • LとRの結果は4桁でなければならないので、文字列を使用する必要はありません.(どうせ4桁は確認しなければなりません)=>いつものように、数字だけで
    • に近づいた.
  • BFS経路探索を行う場合,目標値を最も早く見つけることは難しくない.
    ★その値段でどう行けばいいのかわかりにくいです.
    =>BT配列にpair(前の値、dslr値)を加え、最後にこの値を逆方向に追跡する.
    ~~=>各値の前値をBT配列に入れ、そのまま値を求めて遡及する...2000だと10002が20006002になって2000になるともっと複雑になります~~

    • 2.反例


    1
    0 1000
    SDDLDSLDRDDD
    https://www.acmicpc.net/board/view/65714
    3
    1 10
    775 5421
    2784 9034
    Output
    L
    SSSSDL
    DSLSLDLL
    https://hackids.tistory.com/88

    3.私の回答

    #include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <string>
using namespace std;

bool visited[10001];
pair<int,int> BT[10001];
char outDSLR[5] = {'0', 'D','S','L','R' };
int a,b;
vector<char> path;

int moveLeft(int val) {
	int num[4];

	for (int i = 3; i >=0; i--) {
		num[i] = val % 10;
		val /= 10;
	}
	for (int i = 0; i < 3; i++) {
		swap(num[i], num[i + 1]);
	}

	int ret = num[0];
	for (int i = 1; i < 4; i++) {
		ret *= 10;
		ret += num[i];
	}
	//cout << ret << "\n";
	return ret;
}

int moveRight(int val) {
	int num[4];

	for (int i = 3; i >= 0; i--) {
		num[i] = val % 10;
		val /= 10;
	}
	for (int i = 3; i >0; i--) {
		swap(num[i], num[i - 1]);
	}

	int ret = num[0];
	for (int i = 1; i < 4; i++) {
		ret *= 10;
		ret += num[i];
	}
	//cout << ret << "\n";
	return ret;
}


void BFS(int start) {
	queue<int> q;

	q.push(start);
	BT[start]=make_pair(start,0);
	visited[start] = true;

	while (!q.empty()) {
		int now = q.front();
		q.pop();

		if (now == b) {
			return;
		}
		int dslr[5];
		dslr[1] = (now * 2) % 10000;

		dslr[2] =now- 1;
		if (dslr[2] < 0)	dslr[2] = 9999;
		dslr[3] = moveLeft(now);
		dslr[4] = moveRight(now);

		for (int i = 1; i < 5; i++) {
			if (!visited[dslr[i]]) {
				visited[dslr[i]]=true;
				BT[dslr[i]]=make_pair(now,i);
				q.push(dslr[i]);
			}
		}
		
	}
}

void backtracking(int start) {
	if (start == a)	return;

	path.push_back(outDSLR[BT[start].second]);
	backtracking(BT[start].first);

	return;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int t;
	cin >> t;
	for(int i=0;i<t;i++){
		cin >> a>>b;

		memset(visited, false, sizeof(visited));
		path.clear();
		BFS(a);
		backtracking(b);

		for (int i = path.size() - 1; i >= 0; i--) {
			cout << path[i];
		}
		cout << "\n";
	}

	return 0;
}
    BFSだけを考えると方向を特定しやすいのですが、パスを出力させるのは難しいです.
    Rデータ整理によるデータ分析
    [GIT] Rebase