Q2-蓋房子

2022.11.11 PM 11:00 by CBJ

來源 : 111資訊學科能力競賽複賽-彰雲嘉
標籤 : 窮舉法
難易度 : 3
題目敘述 : 
建商想在一塊m*m的建地上蓋房子,房子有四種樣式可以選擇
                           __     __
    __      ________    __|  |   |  |__
 __|  |__  |__    __|  |__   |   |   __|
|________|    |__|        |__|   |__| 

建地上的每一格都有其對應的成本,求最小成本。

輸入說明 :
首先有一個整數m,代表建地的邊長。
再來就是該建地的內容。

範例測資 : 
範例輸入
4
2 5 2 7
3 2 5 8
1 2 3 9
8 2 1 2
範例輸出
7

測資說明 :
最終的答案應是
  2
1 2   這組,故答案為 1+2+2+2 = 7
  2
解題想法 : 
題目提供一個整數m,表示建地有m*m的大小。
對於每個房子樣式,先定義好其偏移量如下:
                               __     __
    __        ________      __|  |   |  |__
 __|  |__    |__    __|    |__   |   |   __|
|________|      |__|          |__|   |__| 
                              -1,1  -1,0
   -1,1      0,0 0,1 0,2   0,0 0,1   0,0 0,1
0,0 0,1 0,2      1,1           1,1   1,0
                               
P.S 沒有標準答案,要以哪一格當作0,0都可以,只是其他格的偏移量也會隨之改變。

舉例來說,假如0,0那格現在位於(6,7)的位置,則0,1那格會位於(6+0,7+1) = (6,8)的位置,以此類推。

實作上我們會以每個樣式的0,0為主,運用雙層迴圈i和j來走訪整個m*m建地。

為了避免戳到不該戳的陣列位置,走訪時i的範圍跟j的範圍極其重要,以第一種樣式來說,若將0,0放在陣列(0,0)的位置,那當遇到-1,1時,就會去戳到(0-1,0+1) = (-1,1)的位置,但是陣列是沒有-1這個地方的,所以就會出錯,所以我們的i一開始應該從1出發而不是0。
那i的結束點呢? 我們可以發現0,0若位在最底下的位置是可以的,因為沒有 1,0 or 1,1 or 1,2 的case,所以不會戳到超出範圍,那最底下的位置是哪裡呢? 就是m-1。

解決好第一個迴圈i,再來是第二個迴圈j的部分,我們一樣可以像i一樣觀察,若0,0在(x,y)的位置,其他格會不會戳到出界,透過觀察可以發現,j會從0開始出發,因為最左邊的就是0,0,沒有比他更左邊的格子,那結束點呢? 我們可以知道最右邊的格子一定可以走到最邊邊,也就是m-1的地方,而最右邊的格子是0,2,所以0,0最多只能走到(m-1)-2的地方,也就是m-3。

實際轉成程式碼就會像底下這樣:
for(int i=1; i<=m-1; i++){
....for(int j=0; j<=m-3; j++){
........// do something...
....}
}

其中的do something在實作時就會發現,其實根本就是照抄,所以我們只需要稍微修改一下i的起點終點,和j的起點終點,就可以完成所有樣式的處理了!

那回歸到定義偏移量有何用處,就是在已知的0,0去找到剩下三格,題目的要求是將這幾格相加並求出最小值,因此我們會再有一個for迴圈,去將其他格的值抓出來相加,並更新答案。
//C++ language
//solution link(含註解): https://github.com/CBJ0519/CBJsProgramDiary.com/blob/main/%E8%B3%87%E8%A8%8A%E5%AD%B8%E7%A7%91%E8%83%BD%E5%8A%9B%E7%AB%B6%E8%B3%BD/111%E5%BD%B0%E9%9B%B2%E5%98%89/Q2-%E8%93%8B%E6%88%BF%E5%AD%90.cpp

#include<iostream>
#include<vector>
#include<utility>
using namespace std;
int m,base[100][100],ans=1e9;
vector<vector<pair<int,int>>>v={ { {0,0},{0,1},{0,2},{-1,1} },
                                 { {0,0},{0,1},{0,2},{1,1} },
                                 { {0,0},{0,1},{-1,1},{1,1} },
                                 { {0,0},{0,1},{-1,0},{1,0} } };
void solve(int n){
    switch(n){
    case 0:{
        for(int i=1;i<=m-1;i++){
            for(int j=0;j<=m-3;j++){
                int sum=0;
                for(pair<int,int> p:v[n]){
                    int newx=p.first;
                    int newy=p.second;
                    sum += base[i+newx][j+newy];
                }
                ans=min(ans,sum);
            }
        }
    }break;
    case 1:{
        for(int i=0;i<=m-2;i++){
            for(int j=0;j<=m-3;j++){
                int sum=0;
                for(pair<int,int> p:v[n]){
                    int newx=p.first;
                    int newy=p.second;
                    sum += base[i+newx][j+newy];
                }
                ans=min(ans,sum);
            }
        }
    }break;
    case 2:{
        for(int i=1;i<=m-2;i++){
            for(int j=0;j<=m-2;j++){
                int sum=0;
                for(pair<int,int> p:v[n]){
                    int newx=p.first;
                    int newy=p.second;
                    sum += base[i+newx][j+newy];
                }
                ans=min(ans,sum);
            }
        }
    }break;
    case 3:{
        for(int i=1;i<=m-2;i++){
            for(int j=0;j<=m-2;j++){
                int sum=0;
                for(pair<int,int> p:v[n]){
                    int newx=p.first;
                    int newy=p.second;
                    sum += base[i+newx][j+newy];
                }
                ans=min(ans,sum);
            }
        }
    }break;
    }
}
int main(){
    cin>>m;
    for(int i=0;i<m;i++){
        for(int j=0;j<m;j++){
            cin>>base[i][j];
        }
    }
    for(int i=0;i<4;i++){
        solve(i);
    }
    cout<<ans<<"\n";
    return 0;
}

相關文章

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *