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