这个问题需要根据特定的探索规则还原忍者屋的地图结构。关键在于理解深度优先搜索$(DFS)$的探索方式，并将记录序列转换为图结构。

核心数据结构与设计思路

1. 探索记录解析：

   • 使用一个数组$L$存储所有记录数字
   • $l$数组记录每个房间剩余未处理的门数

2. 图结构表示：

   • $A$二维数组存储邻接表，$A[i]$表示与房间$i$相连的所有房间
   • $rooms$映射记录每个距离对应的房间编号

3. 深度优先搜索模拟：

   • 递归函数$dfs$模拟探索过程，处理正数和负数记录
   • 维护当前深度$d$和全局计数器$t$、$n$

核心算法解析

1. 记录处理逻辑：

   • 正数记录：创建新房间，连接当前房间和新房间
   • 负数记录：计算目标房间编号，连接当前房间和目标房间

2. 递归探索：

   • 每次递归增加深度$d$，表示与起始房间的距离
   • 处理完所有门后回溯，保持与$DFS$探索规则一致

3. 图构建：

   • 邻接表中每个节点的连接按升序排列
   • 处理重复边的情况，确保每个门都被正确记录

代码实现

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

vector<int> L;
vector<vector<int> > A; 
map<int, int> rooms;
vector<int> l;
int t, n;

void dfs(int d) {
	int s = n;
	t++;
	while (l[s] > 0 && t < (int)L.size()) {  
		if (L[t] > 0) {
			n++;
			l[s]--;
			l.push_back(L[t] - 1);
			vector<int> temp;
			temp.push_back(s);
			A.push_back(temp);
			A[s].push_back(n);
			rooms[d + 1] = n;
			dfs(d + 1);
		} else if (L[t] < 0) {
			int j = rooms[d + L[t]];
			l[j]--;
			l[s]--;
			A[s].push_back(j);
			A[j].push_back(s);
			t++;
		}
	}
}

int main() {
	int N;
	cin >> N;
	for (int _ = 0; _ < N; ++_) {
		L.clear();
		A.clear();
		rooms.clear();
		l.clear();
		
		int num;
		while (cin >> num && num != 0) {
			L.push_back(num);
		}
		
		A.clear();
		vector<int> empty1;
		vector<int> empty2;
		A.push_back(empty1);
		A.push_back(empty2);
		
		rooms[0] = 1;
		l.push_back(0);
		l.push_back(L[0]);
		t = 0;
		n = 1;
		
		dfs(0);
		
		for (int i = 1; i < (int)A.size(); ++i) {  
			sort(A[i].begin(), A[i].end());
			cout << i;
			for (int j = 0; j < (int)A[i].size(); ++j) { 
				cout << " " << A[i][j];
			}
			cout << endl;
		}
	}
	return 0;
}

复杂度分析

• 时间复杂度：O(m²)，其中m是房间数。每个房间的邻接表需要排序。
• 空间复杂度：O(m²)，主要用于存储邻接表。

注意事项

1. 数组索引：

   • 房间编号从1开始，数组索引0不使用
   • 确保所有数组操作都正确处理索引

2. 递归深度：

   • 由于房间数不超过100，递归深度不会导致栈溢出

3. 重复边处理：

   • 邻接表中允许重复边，确保每个门都被正确记录