[10%] You are optimizing the core engine of an image editing tool called "Smart Lasso". The tool helps users extract objects by automatically finding the best boundary between a Start Pixel (S) and a Target Pixel (T).

The image is represented as a grid of pixels. Each pixel has an associated "Energy Cost" (representing high-frequency noise or weak edges). Here are some rules:

• Movement Rule: From any pixel, you can move to adjacent pixels (Up, Down, Left, Right). Diagonal movement is not allowed.
• Path Cost: The sum of the Energy Costs of all pixels visited on the path (excluding S, but including T).

Energy cost matrix is shown as below (assume the cost of entering T is 0):

$\begin{bmatrix} S & 4 & 5 & 9 & 8 \\ 7 & 9 & 8 & 6 & 9 \\ 3 & 2 & 4 & 1 & 5 \\ 6 & 5 & 6 & 7 & T \end{bmatrix}$

In the following, we will use (row, col) as coordinate representation. Top-left is (0, 0). If two neighbors have the same cost, prioritize the direction in this order: Right → Down → Up → Left

Questions:

(1) [4%] A junior developer implemented a "High-Speed Mode" for the lasso. The logic is simple:

"At every step, the cursor simply snaps to the immediate neighbor with the lowest energy cost to get closer to the target. It does not plan ahead."

Please trace the path generated by this method from S to T and calculate the total cost. (Path Sequence、Total Path Cost)

(2) [4%] Users have complained that the "High-Speed Mode" (from Q4.1) often gets "trapped" in noisy areas or takes expensive detours, failing to find the true object boundary. Your manager asks you to rewrite the core engine. The new requirement is:

"The tool must guarantee finding the mathematically optimal boundary—the path with the absolute minimum Total Cumulative Cost from Start to Target—even if it takes a bit more computation time."

Please trace the path generated by this method from S to T and calculate the total cost. (Path Sequence、Total Path Cost)

(3) [2%] The solution in Q4.2 works great on small grids. However, when applied to a 4K Image (with $N$ pixels), the tool becomes laggy. Profiling reveals the bottleneck is in the Open Set (Priority Queue)—specifically, the operation of repeatedly finding and removing the pixel with the minimum cumulative cost. You are comparing two underlying data structures for this Priority Queue: a simple Unsorted Array vs. a Binary Min-Heap. Please analyze the Time Complexity (Big-O) for the "Extract-Min" operation in both cases.

• Case 1: You use a simple Unsorted Array to store the candidate pixels, the time complexity for Extract-Min is: ______
• Case 2: You switch to a Binary Min-Heap to store the candidate pixels, the time complexity for Extract-Min is: ______