(Aizu 0033) BALL (DFS搜索)

我不是女神ヾ 2022-03-11 00:54 150阅读 0赞

![c6d8117e2949747585c1dc2953fadf7a_v_1551724026][]

図のように二股に分かれている容器があります。1 から 10 までの番号が付けられた10 個の玉を容器の開口部 A から落とし、左の筒 B か右の筒 C に玉を入れます。板 D は支点 E を中心に左右に回転できるので、板 D を動かすことで筒 B と筒 C のどちらに入れるか決めることができます。

開口部 A から落とす玉の並びを与えます。それらを順番に筒 B 又は筒 Cに入れていきます。このとき、筒 B と筒 C のおのおのが両方とも番号の小さい玉の上に大きい玉を並べられる場合は YES、並べられない場合は NO と出力するプログラムを作成してください。ただし、容器の中で玉の順序を入れ替えることはできないものとします。また、続けて同じ筒に入れることができるものとし、筒 B, C ともに 10 個の玉がすべて入るだけの余裕があるものとします。

## Input ##

複数のデータセットが与えられます。１行目にデータセット数 N が与えられます。つづいて、N 行のデータセットが与えられます。各データセットに 10 個の番号が左から順番に空白区切りで与えられます。

## Output ##

各データセットに対して、YES または NO を１行に出力して下さい。

## Sample Input ##

2
    3 1 4 2 5 6 7 8 9 10
    10 9 8 7 6 5 4 3 2 1

## Output for the Sample Input ##

YES
    NO

解题思路:

题目的意思是,将能否将10个球填进左右两个管道里,使球序号的排列顺序是有序的

使用DFS算法一个一个去试即可

#include <iostream>
    #include <algorithm>
    #include <vector>
    using namespace std;
    int ballsBuild[15];
    vector<int> BallsVecLeft, BallsVecRight;
    int cnt = 0;
    bool sflag = false;
    //DFS Algorithm
    void DFS_BALLS(int indexes) {
    	if (indexes == 10) {
    		if (cnt == 10) {
    			for (int i = 1; i < BallsVecLeft.size(); ++i) {
    				if (BallsVecLeft[i - 1] > BallsVecLeft[i]) return;
    			}
    			for (int i = 1; i < BallsVecRight.size(); ++i) {
    				if (BallsVecRight[i - 1] > BallsVecRight[i]) return;
    			}
    			sflag = true;
    		}
    		return;
    	}
    	//DFS优先遍历
    	BallsVecLeft.push_back(ballsBuild[indexes]);
    	cnt++;
    	DFS_BALLS(indexes + 1);
    	BallsVecLeft.pop_back();
    	cnt--;
    	BallsVecRight.push_back(ballsBuild[indexes]);
    	cnt++;
    	DFS_BALLS(indexes + 1);
    	BallsVecRight.pop_back();
    	cnt--;
    }
    int main() {
    	int N;
    	cin >> N;
    	for (int i = 0; i < N; ++i) {
    		sflag = false;
    		for (int j = 0; j < 10; ++j) {
    			cin >> ballsBuild[j];
    		}
    		DFS_BALLS(0);
    		if (sflag) cout << "YES" << endl;
    		else cout << "NO" << endl;
    	}
    
    	return 0;
    }

[c6d8117e2949747585c1dc2953fadf7a_v_1551724026]: https://vj.2vjd.cn/c6d8117e2949747585c1dc2953fadf7a?v=1551724026