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;
}
發佈留言