CF2245H Connect Connect See

You are given a rectangular grid $ a $ consisting of $ n $ rows and $ m $ columns. The $ j $ -th cell in the $ i $ -th row is denoted by $ (i,j) $ . There is a non-negative integer written in every cell. The integer written in cell $ (i,j) $ is denoted by $ a_{i,j} $ . A path $ p $ of length $ k $ on $ a $ is defined as a sequence of cells $ p_0,p_1,\ldots,p_k $ such that $ p_i $ and $ p_{i+1} $ share an edge for every $ 0 \le i \lt k $ , and all $ p_i $ are distinct. The number of turns of a simple path $ p $ of length $ k $ , denoted by $ t(p) $ , is defined as the number of indices $ 1 \le i \lt k $ that satisfy the following condition: - Let $ p_j=(x_j,y_j) $ for $ j \in \{i-1,i,i+1\} $ . Then, both $ x_{i-1} \ne x_{i+1} $ and $ y_{i-1} \ne y_{i+1} $ hold. A path $ p=[(x_0,y_0),(x_1,y_1),\ldots,(x_k,y_k)] $ is considered valid if and only if all of the following conditions hold: - $ k \ge 1 $ . - $ t(p) \le 2 $ . - $ a_{x_0,y_0}=a_{x_k,y_k} $ , $ a_{x_0,y_0} \gt 0 $ , and $ a_{x_i,y_i}=0 $ for every $ 1 \le i \lt k $ . An unordered pair of cells $ (u_1,v_1) $ and $ (u_2,v_2) $ is considered connectable if and only if there exists a valid path $ p $ of length $ k $ such that $ p_0=(u_1,v_1) $ and $ p_k=(u_2,v_2) $ . Find the number of connectable pairs in $ a $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains two integers $ n $ and $ m $ ( $ 1 \le n \le 100 $ , $ 1 \le n \cdot m \le 2 \cdot 10^6 $ ), representing the dimensions of $ a $ . The $ i $ -th of the next $ n $ lines contains $ m $ integers $ a_{i,1}, a_{i,2},\ldots,a_{i,m} $ ( $ 0 \le a_{i,j} \le n \cdot m $ ), representing the $ i $ -th row of $ a $ . It is guaranteed that the sum of $ n \cdot m $ over all test cases does not exceed $ 2 \cdot 10^6 $ .

For each test case, output an integer representing the number of connectable pairs in $ a $ .

In the first and second test cases, there are no connectable pairs in $ a $ . In the third test case, the connectable pairs are: - $ (1,1),(1,2) $ . - $ (1,2),(2,2) $ . - $ (1,1),(2,2) $ . In the sixth test case, there are $ 34 $ connectable pairs. One of them is $ (1,1),(3,3) $ . Note that $ (1,1),(5,5) $ is not a connectable pair, as any path that begins at $ (1,1) $ and ends at $ (5,5) $ has more than $ 2 $ turns.