36. Largest Square (CPE10456, UVA10908) - CPE一顆星解答與說明
CPE一顆星49題解答 - pdf 電子檔，售價 199 元，
購買電子檔可將筆記與完整解答帶著走，
坐車、上課時皆可隨時複習，
不受網路或廣告影響，
若有需要請來信購買 greens2314@gmail.com
題目
- 找出以某一坐標為中心點的最大正方形邊長
- 題目會給一個長方形
- 高度：數字 M，例如 7
- 寬寬：數字 N ，例如 10
- 座標起點，左上角(0, 0) ~ 右下角(M-1, N-1)
- 例如 (0, 0) ~ (6, 9)
- 判斷以座標為中心點，鄰近的字元是否與座標本身的字元一致
- 若一致，表示有找到正方形
輸入說明
- 第一行為測試資料的筆數
- 第二行：
- 長方形的高度 M
- 長方形的寬度 N
- 中心點的數量 Q
- 根據數字 M 與 N 給長方形的資料
- 根據數字 Q 給多筆坐標的資料
- 每行包含兩個整數，代表坐標 (r, c)
輸出說明
- 根據每筆測試資料，輸出
- 長方形的高
- 長方形的寬
- 坐標數量
- 每個坐標最大正方形的邊長
解題技巧
- 二為陣列
- 陣列索引位置
- 字元判斷
解題過程
取得輸入
- 取得資料筆數
- 根據筆數取得：高度、寬度、座標數量
- 印出高度、寬度、座標數量
使用二維陣列儲存矩形的元素
- 宣告二維陣列
- 例如：高度 7 寬度 10 的矩形，要使用 new char[7][10] 的空間來儲存
- 使用兩層 for 迴圈讀取字串與字元
- 題目會根據高度給多筆的字串，其中的字元就是矩形中的元素
- 高度 7 ，有 7 個字串，索引 0 ~ 6
- 寬度 10 ，每筆字串中都有 10 個字元，索引 0 ~ 9
- 可將兩層 for 迴圈產生的索引當作座標，將對應的字元存入二維陣列
根據座標數量，逐一讀取座標位置
- 根據座標位置，取得特定座標所儲存的字元
使用 while 迴圈，以指定座標為中心點，往外找正方形
- 假設一開始會找到合法的正方形，宣告布林值 isValid = true
- 計算周圍的正方形座標
- 移動單位：1，先往旁邊 1 格找是否有相同字元的正方形
- 例如：特定座標 = ( 1, 2 )
- 周圍的正方形座標：特定位置加減移動單位
- ( 1 – 1, 2 – 1 ) ＝( 0 , 1 )
│ │ - ( 1＋1, 2 ＋1 ) ＝( 2 , 3)
- 判斷座標：若座標值小於 0 或大於高度、寬度，為不合法的數值，結束迴圈
檢查正方形四邊的字元是否與特定座標相同
- 使用兩層 for 迴圈產生四個邊的坐標
- 判斷每一個座標的字元是否與特定字元相同
- 若不同則視為不合法的正方形，將 isValid 設為 false，下一次的 while 迴圈會停止
- 例如：特定座標 = ( 1, 2 )
- 周圍的正方形座標：特定位置加減移動單位
- ( 0 , 1 )
│ - ( 2 , 3 )
印出最大的正方形寬
- 注意移動範圍與正方形寬度的關係
- 以座標 (4, 6) 為例子
- 移動範圍 = 1 時，正方形寬度 = 3
- 移動範圍 = 2 時，正方形寬度 = 5
- 最大的正方形寬 = 移動範圍 * 2 - 1
留言
張貼留言