經過一整天辛苦的在派桑地區工作後兩位爪哇公司的銷售員：小敏跟小雁，終於要回家了。但是，他們在回家的路上，看到了一個 n × m 大小的迷宮，(1,1) 位於迷宮的左上角，而 (n,m) 位於迷宮的右下角。在迷宮的每個格子中，都寫著一個數字 aij，代表這個格子的顏色。
而且，在迷宮的入口中，寫了以下的告示：
1. 本迷宮的入口為 (1,1)，出口為 (n,m) 。
2. 在本迷宮中，只能往右或往下走。如果你在 ( i , j )，往右走會變成 ( i + 1 , j )，而往下走會變成 ( i , j + 1 )。
3. 定義一條路徑為：從 (1,1) 走到 (n, m) 的走法。
現在，小敏跟小雁想要走出兩條不同的路徑，使得沿途經過格子顏色依序都是一樣的。身為丙正正公司的程式設計師，你的任務是要寫一支程式，告訴小敏以及小雁，這件事情有沒有可能發生。兩條路徑如果是不同的路徑，代表存在一個格子 ( i , j )，其中一條路徑有經過那個格子，而另外一條路徑沒有經過。
輸入首行為一個正整數 t (1 ≤ t ≤ 10)，代表接下來有 t 筆測試資料。
每筆測試資料的第一行包含兩個正整數 n, m (2 ≤ n, m ≤ 100)，代表小敏與小雁找到的迷宮的大小。接下來的 n 行，每行有 m 個以一個空白隔開的正整數 aij (1 ≤ aij ≤ 100)，代表 ( i , j ) 這個格子的顏色。
如果小敏與小雁找的到兩條不同的路徑,使得沿途依序經過的顏色是一樣的，請輸出 “Yes” (不含引號) 於一行；否則請輸出 “No” (不含引號) 於一行。
#test input 1: 3 2 4 1 2 3 4 5 3 4 5 2 2 1 2 2 3 2 2 1 3 2 1 #test input 2: 2 2 5 1 3 4 5 2 1 4 4 6 2 4 3 8 4 4 4 4 3 4 3 2 4 2 5
#test output 1: Yes Yes No #test output 2: Yes Yes
dp, brute force, constructive algorithm (CF 1500)
19% 的測資滿足 n=2，m=2
32% 的測資滿足 n=2，m≤30
29% 的測資滿足 n≤30，m≤30
20% 的測資滿足 n≤100，m≤100
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||