Source Code Explanation: main.cpp

This document provides a line-by-line explanation of the main.cpp file in both English and Chinese.
本文档提供了 main.cpp 文件的中英双语逐行解释。

1. Includes and Namespaces (引入与命名空间)

1: #include <fstream>
2: #include <iostream>
3: #include <sstream>
4: #include <string>
5: #include <vector>
6: 
7: using namespace std;

• Lines 1-5:
  • EN: Includes standard C++ libraries. <fstream> for file I/O, <iostream> for console I/O, <sstream> for string parsing, <string> for string manipulation, and <vector> for dynamic arrays.
  • ZH: 引入标准 C++ 库。<fstream> 用于文件读写，<iostream> 用于控制台输入输出，<sstream> 用于字符串解析，<string> 用于字符串操作，<vector> 用于动态数组。
• Line 7:
  • EN: Brings the entire standard library namespace into the current scope, allowing usage of vector instead of std::vector.
  • ZH: 引入标准库命名空间，允许直接使用 vector 而不是 std::vector。

2. Utility Templates (实用模板函数)

9: /*
10:  * Swaps the values of two variables.
11:  */
12: template <typename T>
13: void my_swap(T& a, T& b)
14: {
15:     T tmp = a;
16:     a = b;
17:     b = tmp;
18: }

• Lines 12-18:
  • EN: A template function my_swap that swaps the values of two variables using a temporary variable tmp. Used to avoid including the <algorithm> library.
  • ZH: 模板函数 my_swap，使用临时变量 tmp 交换两个变量的值。这是为了避免引入 <algorithm> 库而手动实现的。

20: /*
21:  * In-place reverses the elements of a vector within the range [first, last).
22:  */
23: template <typename T>
24: void my_reverse(vector<T>& v, int first, int last)
25: {
26:     --last;
27:     while (first < last) {
28:         my_swap(v[first], v[last]);
29:         ++first;
30:         --last;
31:     }
32: }

• Lines 23-32:
  • EN: A template function my_reverse that reverses elements in a vector v between indices first (inclusive) and last (exclusive) by repeatedly swapping the outer elements and moving inwards.
  • ZH: 模板函数 my_reverse，通过不断交换外侧元素并向内收缩，来反转数组 v 在 [first, last) 范围内的元素。

34: /*
35:  * In-place reverses the entire vector.
36:  */
37: template <typename T>
38: void my_reverse_all(vector<T>& v)
39: {
40:     my_reverse(v, 0, static_cast<int>(v.size()));
41: }

• Lines 37-41:
  • EN: A wrapper function my_reverse_all that reverses the entire vector from index 0 to its full size.
  • ZH: 包装函数 my_reverse_all，调用 my_reverse 来反转整个数组（从索引 0 到数组全长）。

3. Data Structures (数据结构)

45: /*
46:  * Manages a set of points based on a 2D boolean array to check grid coordinate occupancy in O(1) time.
47:  */
48: struct PointSet {
49:     int n;
50:     vector<vector<bool> > used;
51: 
52:     explicit PointSet(int grid_n)
53:         : n(grid_n), used(grid_n, vector<bool>(grid_n, false)) {}
54: 
55:     bool insert(int x, int y)
56:     {
57:         if (used[y][x]) return false;
58:         used[y][x] = true;
59:         return true;
60:     }
61: };

• Lines 48-61:
  • EN: Defines PointSet, a struct acting like a hash set. It uses a 2D boolean grid (used) of size $n \times n$ initialized to false (Line 53). The insert method (Lines 55-60) returns false if the coordinate is already set (collision detected), otherwise it marks it true and returns true.
  • ZH: 定义了 PointSet 结构体，它的作用类似于哈希集合。它使用一个大小为 $n \times n$ 的二维布尔数组 used，初始全为 false（第53行）。insert 方法（55-60行）如果发现坐标已经被标记，则返回 false（检测到冲突）；否则标记为 true 并返回 true。

64: struct Point {
65:     int x;
66:     int y;
67:     Point() : x(0), y(0) {}
68:     Point(int x_, int y_) : x(x_), y(y_) {}
69:     bool operator==(const Point& o) const
70:     {
71:         return x == o.x && y == o.y;
72:     }
73: };

• Lines 64-73:
  • EN: Defines Point representing a 2D coordinate with x and y. Includes a default constructor (Line 67), a parameterized constructor (Line 68), and an overloaded equality operator == (Lines 69-72) to compare two points easily.
  • ZH: 定义了 Point 结构体，代表二维坐标 x 和 y。包含默认构造函数（第67行）、带参构造函数（第68行），以及重载的等于操作符 ==（69-72行），方便直接比较两个点是否相同。

76: struct Net {
77:     int   id;
78:     Point source;
79:     Point sink;
80:     Net() : id(0) {}
81: };

• Lines 76-81:
  • EN: Defines Net, representing a wire connection requirement. Contains a unique id, a starting point (source), and an ending point (sink).
  • ZH: 定义了 Net（网线），代表一条布线需求。包含唯一标识 id、起点 source 和终点 sink。

83: struct Problem {
84:     int                n;
85:     vector<Point> obstructions;
86:     vector<Net>   nets;
87:     Problem() : n(0) {}
88: };

• Lines 83-88:
  • EN: Defines Problem to hold the parsed input data: grid size n, a list of fixed obstacle coordinates obstructions, and a list of wire requests nets.
  • ZH: 定义了 Problem（问题）结构体，用于存放解析后的输入数据：网格大小 n、固定障碍物坐标列表 obstructions 以及布线需求列表 nets。

90: struct WaveRecord {
91:     int                level;
92:     vector<Point> cells;
93:     WaveRecord() : level(0) {}
94: };

• Lines 90-94:
  • EN: Defines WaveRecord, used strictly for visualization. It records the BFS distance (level) and the list of points (cells) discovered at that distance.
  • ZH: 定义了 WaveRecord（波纹记录），仅用于可视化。记录了 BFS 搜索的距离层级 level，以及在该距离下发现的坐标点列表 cells。

96: struct NetRoute {
97:     bool                    success;
98:     vector<Point>      path;
99:     vector<WaveRecord> waves;
100:    NetRoute() : success(false) {}
101: };

• Lines 96-101:
  • EN: Defines NetRoute to store the result of routing a single net. success indicates if a path was found. path holds the final path coordinates. waves stores the BFS history.
  • ZH: 定义了 NetRoute（单线布线结果）。success 标记是否成功找到路径，path 保存最终的路径坐标，waves 存储 BFS 搜索的历史。

103: struct RouteAttempt {
104:     vector<NetRoute> net_routes;
105:     int                   routed_count;
106:     int                   total_wirelength;
107:     vector<int>      order;
108:     RouteAttempt() : routed_count(0), total_wirelength(0) {}
109: };

• Lines 103-109:
  • EN: Defines RouteAttempt to store the result of an entire board routing. Holds individual net results (net_routes), the total number of successful nets (routed_count), the sum of all path lengths (total_wirelength), and the sequence order in which nets were processed.
  • ZH: 定义了 RouteAttempt（全局布线尝试结果）。保存单线结果列表 net_routes，成功布通的总线数 routed_count，所有连线的总长度 total_wirelength，以及进行布线时采用的网络顺序 order。

4. Constants and Utilities (常量与辅助函数)

111: const int FREE        = -1;
112: const int OBSTRUCTION = -2;
113: const int TERMINAL    = -3;

• Lines 111-113:
  • EN: Defines status constants for grid cells. Anything $\ge 0$ implies the cell is occupied by a wire with that Net ID.
  • ZH: 定义了网格单元格的状态常量。任何 $\ge 0$ 的值代表该格子被对应 ID 的网线占用。

115: /*
116:  * Trims leading and trailing whitespace characters (including spaces, tabs, and newlines) from a string.
117:  */
118: string trim(const string& s)
119: {
120:     const size_t first = s.find_first_not_of(" \t\r\n");
121:     if (first == string::npos) return "";
122:     const size_t last = s.find_last_not_of(" \t\r\n");
123:     return s.substr(first, last - first + 1);
124: }

• Lines 118-124:
  • EN: A function trim that removes leading (Line 120) and trailing (Line 122) whitespaces from a string. If the string is empty or only whitespace, it returns "" (Line 121). Finally, it extracts the trimmed substring (Line 123).
  • ZH: 字符串去空格函数 trim。寻找第一个非空格字符的位置（第120行）和最后一个非空格字符的位置（第122行）。如果全是空格则返回空串（第121行）。最后截取并返回去除了首尾空格的子串（第123行）。

126: /*
127:  * Checks if the given coordinate (x, y) is within the boundaries of the n x n grid.
128:  */
129: bool in_bounds_n(int x, int y, int n)
130: {
131:     return x >= 0 && y >= 0 && x < n && y < n;
132: }

• Lines 129-132:
  • EN: A function in_bounds_n that returns true only if $x$ and $y$ are $\ge 0$ and strictly less than the grid size $n$.
  • ZH: 边界检查函数 in_bounds_n，当坐标 $x$ 和 $y$ 大于等于0且严格小于网格大小 $n$ 时，返回 true。

5. Input Parsing (输入解析)

137: bool read_netlist(const string& filename, Problem& prob)
138: {
139:     ifstream input(filename.c_str());
140:     if (!input) {
141:         cerr << "Error: Cannot open netlist: " << filename << '\n';
142:         return false;
143:     }

• Lines 137-143:
  • EN: Function read_netlist opens the file. If opening fails, prints an error to cerr and returns false.
  • ZH: 解析函数 read_netlist 打开文件。如果打开失败，向 cerr 输出错误并返回 false。

145:     string line;
146:     bool size_read = false;
147:     int  net_id    = 0;
148:     int  line_no   = 0;

• Lines 145-148:
  • EN: Initializes variables to store the current line, a flag to check if grid size was read, a counter for net IDs, and a line number counter for error reporting.
  • ZH: 初始化变量：当前行字符串、是否已读取网格大小的标记、网络 ID 计数器，以及用于报错的行号计数器。

150:     while (getline(input, line)) {
151:         ++line_no;
152:         size_t comment = line.find("//");
153:         if (comment != string::npos) line = line.substr(0, comment);
154:         line = trim(line);
155:         if (line.empty()) continue;
156: 
157:         istringstream iss(line);

• Lines 150-157:
  • EN: Loops over every line in the file. Increments line number (151). Finds and removes any inline // comments (152-153). Trims whitespace (154) and skips empty lines (155). Wraps the cleaned line in a string stream iss for parsing (157).
  • ZH: 循环读取文件每一行。行号加一（151）。查找并截断 // 注释部分（152-153）。去空格（154）并跳过空行（155）。将清理后的行放入字符串流 iss 准备解析（157）。

159:         if (!size_read) {
160:             if (!(iss >> prob.n) || prob.n <= 0) {
161:                 cerr << "Error: Invalid grid size on line " << line_no << '\n';
162:                 return false;
163:             }
164:             string extra;
165:             if (iss >> extra) {
166:                 cerr << "Error: Unexpected token '" << extra << "' in: " << line << '\n';
167:                 return false;
168:             }
169:             size_read = true;
170:             continue;
171:         }

• Lines 159-171:
  • EN: If grid size hasn't been read yet, parses the first integer into prob.n and validates it's $> 0$ (160-163). Checks if there is garbage data trailing on the same line (164-168). Marks size as read and moves to the next line (169-170).
  • ZH: 如果还没读取过网格大小，尝试提取第一个整数赋值给 prob.n 并验证其 $> 0$（160-163）。检查同行后面是否有多余的无效字符（164-168）。标记大小已读取并跳过当前循环（169-170）。

173:         string kw;
174:         iss >> kw;
175: 
176:         if (kw == "obstruction") {
177:             Point q;
178:             if (!(iss >> q.x >> q.y)) {
179:                 cerr << "Error: Malformed obstruction: " << line << '\n';
180:                 return false;
181:             }
182:             string extra;
183:             if (iss >> extra) { ... return false; }
184:             prob.obstructions.push_back(q);

• Lines 173-187 (abbreviated):
  • EN: Reads the keyword (kw). If it's "obstruction", parses the $X$ and $Y$ coordinates into point q, performs validation, and adds it to prob.obstructions.
  • ZH: 读取关键字 kw。如果是 "obstruction"（障碍物），解析 $X$ 和 $Y$ 坐标至点 q，进行格式校验后将其推入 prob.obstructions 列表。

189:         } else if (kw == "net") {
190:             Net net;
191:             net.id = net_id++;
192:             if (!(iss >> net.source.x >> net.source.y >> net.sink.x >> net.sink.y)) {
193:                 cerr << "Error: Malformed net: " << line << '\n';
194:                 return false;
195:             }
196:             string extra;
197:             if (iss >> extra) { ... return false; }
198:             prob.nets.push_back(net);

• Lines 189-201 (abbreviated):
  • EN: If keyword is "net", initializes a Net, assigns an auto-incrementing ID (191), parses 4 integers (source $X,Y$ and sink $X,Y$), validates, and adds to prob.nets.
  • ZH: 如果关键字是 "net"（网线），初始化一个 Net，分配自增的 ID (191)，解析 4 个整数（起点 $X,Y$ 和终点 $X,Y$），校验后推入 prob.nets 列表。

203:         } else {
204:             cerr << "Error: Unknown keyword '" << kw << "' on line " << line_no << '\n';
205:             return false;
206:         }
207:     }

• Lines 203-207:
  • EN: Rejects any unknown keywords and loops until EOF.
  • ZH: 拒绝任何未知的关键字，一直循环直到文件读取完毕 (EOF)。

209:     if (!size_read) { ... }
213:     if (prob.nets.empty()) { ... }

• Lines 209-216:
  • EN: Final file checks to ensure the grid size was found and at least one net exists.
  • ZH: 文件结束后的最终检查，确保成功读取了网格大小，且至少包含一条连线。

218:     PointSet obs_set(prob.n);
219:     for (size_t i = 0; i < prob.obstructions.size(); ++i) {
220:         const Point& q = prob.obstructions[i];
221:         if (!in_bounds_n(q.x, q.y, prob.n)) { ... return false; }
225:         if (!obs_set.insert(q.x, q.y)) { ... return false; }
229:     }

• Lines 218-229:
  • EN: Creates a PointSet for obstructions. Iterates over all parsed obstructions to ensure they are inside grid boundaries (221) and that there are no overlapping/duplicate obstructions (225).
  • ZH: 为障碍物创建一个 PointSet 集合。遍历所有解析出的障碍物，确保它们没有越界（221），且不存在重复的障碍物坐标（225）。

231:     PointSet term_set(prob.n);
232:     for (size_t i = 0; i < prob.nets.size(); ++i) {
233:         const Net& net = prob.nets[i];
234:         if (!in_bounds_n(net.source.x, net.source.y, prob.n) ||
235:                 !in_bounds_n(net.sink.x,   net.sink.y,   prob.n)) { ... return false; }
239:         if (net.source == net.sink) { ... return false; }
243:         const Point terminals[2] = { net.source, net.sink };
244:         for (int t = 0; t < 2; ++t) {
245:             if (!term_set.insert(terminals[t].x, terminals[t].y)) { ... return false; }
249:         }
250:     }
251:     return true;
252: }

• Lines 231-252:
  • EN: Uses another PointSet for terminals. Ensures source and sink are strictly inside bounds (234), source and sink are not the same point (239), and no two distinct nets share a terminal cell (245). Returns true if all validations pass.
  • ZH: 使用另一个 PointSet 检查终端。确保起点和终点都在网格内（234），起点和终点不能是同一个格子（239），且没有任何两条网线共享同一个终端格子（245）。如果所有校验通过，返回 true。

6. Core Algorithm: Lee-Moore Router (核心算法)

259: NetRoute lee_route(const Problem& p,
260:                    const Net& net,
261:                    const vector<vector<int> >& occupied)
262: {

• Lines 259-262:
  • EN: Function lee_route takes the problem context, the target net, and the read-only occupied grid to run a BFS.
  • ZH: lee_route 函数接收问题上下文、目标 net，以及只读的 occupied 网格占用矩阵，准备执行 BFS (广度优先搜索)。

263:     static const int dx[4] = {1, -1, 0, 0};
264:     static const int dy[4] = {0, 0, 1, -1};
265: 
266:     vector<vector<int> >   labels(p.n, vector<int>(p.n, -1));
267:     vector<vector<Point> > parent(p.n, vector<Point>(p.n, Point(-1, -1)));

• Lines 263-267:
  • EN: dx, dy define movement offsets (Right, Left, Down, Up). labels stores the BFS step distance (initialized to -1 unvisited). parent stores the predecessor point to trace the final path back.
  • ZH: dx, dy 定义了移动偏移量（右、左、下、上）。labels 二维数组记录 BFS 步数距离（初始化为 -1 表示未访问）。parent 二维数组记录前驱节点，用于最后的回溯路径。

269:     vector<Point> current_wave;
270:     current_wave.push_back(net.source);
271:     labels[net.source.y][net.source.x] = 0;

• Lines 269-271:
  • EN: Initializes the BFS queue (current_wave) with the net's source point, and sets its distance label to 0.
  • ZH: 初始化 BFS 队列 (current_wave) 并推入网线的起点，将其距离标签设为 0。

273:     NetRoute result;
274:     WaveRecord wr0;
275:     wr0.level = 0;
276:     wr0.cells = current_wave;
277:     result.waves.push_back(wr0);

• Lines 273-277:
  • EN: Prepares the result structure and records the very first "wave" (level 0, just the source point) for visualization.
  • ZH: 准备 result 结果结构体，并记录最初的“波纹”（level 0，仅包含起点）用于可视化。

279:     bool path_exists = false;
280:     int  level       = 1;
281: 
282:     while (!current_wave.empty() && !path_exists) {
283:         vector<Point> next_wave;

• Lines 279-283:
  • EN: BFS loop condition: run as long as there are cells to explore and the target hasn't been found. next_wave collects valid neighbors for the next iteration.
  • ZH: BFS 循环条件：只要当前波纹还有点且尚未找到终点，就继续扩展。next_wave 用于收集下一轮迭代的合法邻居点。

285:         for (size_t ci = 0; ci < current_wave.size() && !path_exists; ++ci) {
286:             const Point& cur = current_wave[ci];
287: 
288:             for (int d = 0; d < 4; ++d) {
289:                 Point nb(cur.x + dx[d], cur.y + dy[d]);

• Lines 285-289:
  • EN: Iterates over every cell in current_wave. For each cell, checks all 4 orthogonal neighboring cells (nb).
  • ZH: 遍历 current_wave 中的每一个格子。对于每个格子，向它的 4 个正交方向探索邻居节点 (nb)。

291:                 if (!in_bounds_n(nb.x, nb.y, p.n)) continue;
292:                 if (labels[nb.y][nb.x] != -1)       continue;

• Lines 291-292:
  • EN: Legality checks: Skip if the neighbor is out of bounds (291) or has already been visited (292).
  • ZH: 合法性检查：如果邻居越界（291），或者已经被访问过（292），则跳过。

294:                 const bool own_pin = (nb == net.source || nb == net.sink);
295:                 if (occupied[nb.y][nb.x] != FREE && !own_pin) continue;

• Lines 294-295:
  • EN: Skip if the cell is blocked by an obstruction or another net's wire/terminal. However, entering its own source or sink (own_pin) is strictly allowed.
  • ZH: 检查碰撞：如果该格子被障碍物、其它网线或终点占据则跳过。但是，如果是它自己的起点或终点 (own_pin)，则是绝对允许进入的。

297:                 labels[nb.y][nb.x] = level;
298:                 parent[nb.y][nb.x] = cur;
299:                 next_wave.push_back(nb);
300: 
301:                 if (nb == net.sink) {
302:                     path_exists = true;
303:                     break;
304:                 }
305:             }
306:         }

• Lines 297-306:
  • EN: Mark the neighbor with the current level, set its predecessor (parent), and add it to next_wave (297-299). If this neighbor is the destination sink, stop the search immediately by setting path_exists = true (301-304).
  • ZH: 为邻居节点打上当前的距离标签 level，记录其前驱节点 (parent)，并加入到 next_wave 队列中（297-299）。如果发现这个邻居正是目标 sink，立即设置 path_exists = true 以终止搜索（301-304）。

308:         if (!next_wave.empty()) {
309:             WaveRecord wr;
310:             wr.level = level;
311:             wr.cells = next_wave;
312:             result.waves.push_back(wr);
313:         }
314:         current_wave = next_wave;
315:         ++level;
316:     }

• Lines 308-316:
  • EN: Saves the newly discovered next_wave into the result for visualization. Then makes next_wave the current_wave for the next loop iteration, and increments the distance level.
  • ZH: 将新发现的一圈 next_wave 保存到结果中以便进行动画可视化。然后将 next_wave 交接给 current_wave 进入下一轮循环，并将距离 level 加一。

318:     if (!path_exists) return result;
319: 
320:     Point cur = net.sink;
321:     while (!(cur == net.source)) {
322:         result.path.push_back(cur);
323:         cur = parent[cur.y][cur.x];
324:     }
325:     result.path.push_back(net.source);
326: 
327:     my_reverse_all(result.path);
328:     result.success = true;
329:     return result;
330: }

• Lines 318-330:
  • EN: If no path was found, returns failure early (318). Otherwise, performs traceback: starts at the sink and follows parent pointers back to the source, appending points to result.path (320-325). The path is then reversed (so it goes Source $\rightarrow$ Sink) using my_reverse_all (327). Marks as success and returns.
  • ZH: 如果没找到路径，提前返回失败结果（318）。否则，执行 回溯 (Traceback)：从 sink 开始，顺着 parent 指针一路找回 source，并将途经点加入 result.path（320-325）。此时路径是反向的，调用 my_reverse_all 将其翻转为起点到终点的正向顺序（327）。标记成功并返回结果。

7. Multi-Net Sequence Routing (多网络顺序布线)

336: vector<vector<int> > make_initial_occupancy(const Problem& p)
337: {
338:     vector<vector<int> > occ(p.n, vector<int>(p.n, FREE));
339:     for (size_t i = 0; i < p.obstructions.size(); ++i)
340:         occ[p.obstructions[i].y][p.obstructions[i].x] = OBSTRUCTION;
341:     for (size_t i = 0; i < p.nets.size(); ++i) {
342:         occ[p.nets[i].source.y][p.nets[i].source.x] = TERMINAL;
343:         occ[p.nets[i].sink.y  ][p.nets[i].sink.x  ] = TERMINAL;
344:     }
345:     return occ;
346: }

• Lines 336-346:
  • EN: Function make_initial_occupancy generates a clean routing board. Fills an $N \times N$ matrix with FREE, stamps OBSTRUCTION at obstacle coordinates, and marks all net start/end points as TERMINAL.
  • ZH: make_initial_occupancy 函数生成一个干净的布线底板。初始化一个全是 FREE 的矩阵，在障碍物坐标上打上 OBSTRUCTION 标记，并将所有网线的首尾位置标记为 TERMINAL。

352: RouteAttempt route_in_order(const Problem& p, const vector<int>& order)
353: {
354:     vector<vector<int> > occ = make_initial_occupancy(p);
355:     RouteAttempt result;
356:     result.net_routes.resize(p.nets.size());
357:     result.order = order;

• Lines 352-357:
  • EN: route_in_order routes all nets based on a specific queue order. It creates a fresh board (occ) and prepares the result tracking object.
  • ZH: route_in_order 按照指定的队列顺序 order 对所有网线进行布线。它创建一个干净的底板 occ，并准备用于记录结果的 result 对象。

359:     for (size_t oi = 0; oi < order.size(); ++oi) {
360:         int        idx = order[oi];
361:         const Net& net = p.nets[static_cast<size_t>(idx)];
362:         NetRoute   route = lee_route(p, net, occ);

• Lines 359-362:
  • EN: Iterates through the provided order array, fetching the corresponding Net, and invokes lee_route for it on the shared grid occ.
  • ZH: 遍历指定的 order 数组，抓取对应的网线 Net，并在共享底板 occ 上为其调用 lee_route 进行布线。

364:         if (route.success) {
365:             ++result.routed_count;
366:             result.total_wirelength += static_cast<int>(route.path.size()) - 1;
367:             for (size_t pi = 0; pi < route.path.size(); ++pi) {
368:                 const Point& q = route.path[pi];
369:                 if (!(q == net.source) && !(q == net.sink))
370:                     occ[q.y][q.x] = idx;
371:             }
372:         }
373:         result.net_routes[static_cast<size_t>(idx)] = route;
374:     }
375:     return result;
376: }

• Lines 364-376:
  • EN: If routing succeeds, it increments routed_count and adds the path length (vertices minus 1) to total_wirelength (365-366). Crucially, it commits the wire to the grid occ by stamping the net's ID on every path cell (excluding endpoints) so later nets cannot pass through it (367-371). Saves the route and returns.
  • ZH: 如果布线成功，成功计数 routed_count 加一，并将线长加入总线长 total_wirelength 中（365-366）。最关键的是，它将这条连线固化到底板 occ 上，在路径途径的每一个格子（除首尾）打上这条网线的 ID。这样后续的网线就无法再穿过这里了（367-371）。保存单线结果并最终返回全局结果。

8. Retry Strategy Manager (重试策略管理器)

382: bool better(const RouteAttempt& a, const RouteAttempt& b)
383: {
384:     if (a.routed_count != b.routed_count) return a.routed_count > b.routed_count;
385:     return a.total_wirelength < b.total_wirelength;
386: }

• Lines 382-386:
  • EN: A comparator function better that ranks routing attempts. Priority 1: Maximize successfully routed nets. Priority 2 (Tie-breaker): Minimize total wirelength.
  • ZH: 比较函数 better，用于评判哪次布线尝试更优。优先级1：成功布通的线数越多越好。优先级2（平局决胜）：总线长越短越好。

396: RouteAttempt route_with_retries(const Problem& p)
397: {
398:     const int N = static_cast<int>(p.nets.size());
399: 
400:     vector<int> order(static_cast<size_t>(N));
401:     for (int i = 0; i < N; ++i)
402:         order[static_cast<size_t>(i)] = i;
403: 
404:     RouteAttempt best = route_in_order(p, order);
405:     if (best.routed_count == N) return best;

• Lines 396-405:
  • EN: Function route_with_retries implements the "Failed-Net Promotion" strategy. It starts by routing nets in sequential order 0, 1, 2... (400-402). It runs route_in_order. If all $N$ nets succeed on the first try, it exits immediately (405).
  • ZH: route_with_retries 函数实现了“失败置顶重启”策略。它首先按照默认序号 0, 1, 2... 尝试布线 (400-402)。调用 route_in_order 后，如果 $N$ 条线第一次就全成功了，直接退出返回结果 (405)。

407:     int max_retries = N;
408:     for (int retry = 0; retry < max_retries; ++retry) {
409:         int failed_net = -1;
410:         for (int i = 0; i < N; ++i) {
411:             if (!best.net_routes[static_cast<size_t>(i)].success) {
412:                 failed_net = i;
413:                 break;
414:             }
415:         }
416:         if (failed_net == -1) break;

• Lines 407-416:
  • EN: Sets a retry limit to $N$ to prevent infinite loops (407). In each loop, it searches best.net_routes to find the ID of the first net that failed (410-415).
  • ZH: 设定最大重试次数为 $N$，防止死循环 (407)。在循环中，扫描 best.net_routes 找到第一条遭遇布线失败的网线 ID (410-415)。

418:         /* Move failed_net to the front of the order */
419:         vector<int> new_order;
420:         new_order.push_back(failed_net);
421:         for (size_t i = 0; i < order.size(); ++i) {
422:             if (order[i] != failed_net) {
423:                 new_order.push_back(order[i]);
424:             }
425:         }
426:         order = new_order;

• Lines 418-426:
  • EN: Priority Promotion: Constructs a new_order array. It pushes the failed_net to index 0 (highest priority), then loops through the previous order and appends all other nets in their existing relative sequence.
  • ZH: 优先级提权：构建一个新的队列 new_order。它将刚刚失败的 failed_net 强行排在第 0 位（最高优先级），然后遍历旧队列，将其它网线按原先的相对顺序跟在后面。

428:         RouteAttempt attempt = route_in_order(p, order);
429:         if (better(attempt, best)) {
430:             best = attempt;
431:         }
432:         if (best.routed_count == N) break;
433:     }
434:     return best;
435: }

• Lines 428-435:
  • EN: Routes the grid completely from scratch using the updated order (428). If this new attempt is objectively better than previous attempts, updates best (429-431). Exits early if perfection ($N$ routes) is achieved (432). Returns the best result.
  • ZH: 使用这个更新后的队列 order 从零开始重新布线整个网格 (428)。如果这次的新成绩通过 better 函数评判优于历史最佳，则更新 best (429-431)。如果某次重试达到了 $N$ 根线全通的满分成绩，提前终止重试 (432)。最终返回全局最佳结果。

9. Output Formatting (输出格式化)

441: void write_result(const Problem& p, const RouteAttempt& result)
442: {
443:     cout << "grid " << p.n << '\n';
444:     for (size_t i = 0; i < p.obstructions.size(); ++i)
445:         cout << "obstruction " << p.obstructions[i].x << ' ' << p.obstructions[i].y << '\n';
446: 
447:     cout << "order";
448:     for (size_t i = 0; i < result.order.size(); ++i) cout << ' ' << result.order[i];
449:     cout << '\n';

• Lines 441-449:
  • EN: write_result formats data for the Python visualizer via stdout. Prints grid size, all obstructions, and the final tested routing order.
  • ZH: write_result 专门将数据格式化输出到 stdout，供 Python 可视化脚本解析。打印网格大小、所有障碍物位置，以及最终采用的布线 order 顺序。

451:     for (size_t i = 0; i < p.nets.size(); ++i) {
452:         const Net&      net   = p.nets[i];
453:         const NetRoute& route = result.net_routes[i];
454: 
455:         cout << "net " << net.id ...

• Lines 451-474 (abbreviated):
  • EN: Loops through every net. Prints its ID, source, sink, and whether it "routed" or "failed". Then prints all wave levels for animation. Finally, if successful, prints the actual path coordinates.
  • ZH: 遍历每一根网线。打印它的 ID、起点、终点，以及状态是 "routed" 还是 "failed"。接着打印所有用于绘制动画的扩散波纹 wave 记录。最后，如果布线成功，打印真实的 path 路径坐标序列。

476:     cout << "summary " << result.routed_count << ' ' << p.nets.size()
477:          << ' ' << result.total_wirelength << '\n';
478: }

• Lines 476-478:
  • EN: Prints the final numerical summary line: <success_count> <total_nets> <total_wirelength>.
  • ZH: 打印最终的数值统计行 summary：<成功数> <总数> <总线长>。

10. Main Entry Point (主函数入口)

483: int main(int argc, char* argv[])
484: {
485:     if (argc != 2) {
486:         cerr << "Usage: " << argv[0] << " <netlist>\n";
487:         return 1;
488:     }
489:     const string in_file = argv[1];

• Lines 483-489:
  • EN: Program entry. Verifies exactly 1 command-line argument is passed (the netlist file path).
  • ZH: 程序主入口。校验是否正好传入了 1 个命令行参数（即 netlist 文件路径）。

491:     Problem prob;
492:     if (!read_netlist(in_file, prob)) {
493:         return 1;
494:     }

• Lines 491-494:
  • EN: Instantiates a Problem and parses the file. Exits if parsing fails.
  • ZH: 实例化一个 Problem 对象并读取解析文件。如果解析失败则退出。

497:     const RouteAttempt result = route_with_retries(prob);
498:     write_result(prob, result);

• Lines 497-498:
  • EN: Kicks off the entire algorithmic process via route_with_retries, then pipes the best result to write_result.
  • ZH: 通过 route_with_retries 启动整个算法流程进行布线，然后把得到的最佳结果交给 write_result 打印输出。

501:     cerr << "\n--- Run Info ---\n";
502:     cerr << "Routed " << result.routed_count << " of " << prob.nets.size() << " nets.\n";
503:     cerr << "Total wirelength: " << result.total_wirelength << "\n";
504:     cerr << "Selected order:";
505:     for (size_t i = 0; i < result.order.size(); ++i)
506:         cerr << ' ' << result.order[i];
507:     cerr << "\n";
508: 
509:     return 0;
510: }

• Lines 501-510:
  • EN: Prints a human-readable summary to standard error (cerr). Using cerr prevents this debug text from mixing with the stdout text expected by the visualization pipeline.
  • ZH: 向标准错误流 (cerr) 打印一份给人看的文本统计摘要。使用 cerr 能够防止这些调试信息污染标准输出 (stdout)，以免干扰 Python 可视化脚本的正常读取。程序正常结束返回 0。