[C++]白峻14725号:蟻の穴

質問リンク

14725号:蟻の穴

問題の概要

ロボットはアリが穴に登ったときに見つけた食べ物の情報を与えます.これらの食べ物情報に基づいて蟻の穴の形態を出力しなければならない.

方法

「文字列アルゴリズム1」では、KMPだけを勉強して、文字列をもっと見ないで、せっかく新しいことを学びました.この問題はtraという資料構造によって解決された.
まず、マッピングされたキーが文字列であり、valueが構造体ポインタである構造体を宣言します.サブノードを接続する場合、new演算子で構造体を作成し、ポインタ変数に接続し、ポインタ変数をマッピングに挿入します.mapを使用しないのは、mapが内部で自動的にソートされ、アルファベット順に出力されるからです.
ロボットがナビゲーション中に遭遇した要素を挿入する場合は、これらの要素をベクトルに保存し、再帰呼び出しで挿入できます.現在のインデックスの文字列がmapの内部にある場合は、keyに対応するvalueがすぐに呼び出され、ない場合はサブノードが作成され、接続され、再呼び出されます.
要素を出力する場合は、通常のDFSに近似的にアクセスするだけでよい.出力が終了したノードはすべて削除されます.

コード#コード#

#include <bits/stdc++.h>

using namespace std;

struct Trie {
	map<string, Trie*> m;

	void insert(vector<string>& v, int idx) {
		if (idx == v.size())
			return;

		if (m.find(v[idx]) == m.end()) {
			Trie* trie = new Trie;
			m.insert({ v[idx], trie });
		}

		m[v[idx]]->insert(v, idx + 1);
	}

	void dfs(int d) {
		for (auto& i : m) {
			for (int j = 0; j < d; j++)
				cout << "--";
			cout << i.first << '\n';
			i.second->dfs(d + 1);
			delete i.second;
		}
	}
};

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

	int n;
	cin >> n;

	Trie* root = new Trie;
	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;

		vector<string> v(num);
		for (int j = 0; j < num; j++)
			cin >> v[j];
		root->insert(v, 0);
	}

	root->dfs(0);
	delete root;
	return 0;
}