npsc 2013試題 A. 挑食的大胃王

林宇翔 · 發表於 2014-8-25 14:05:05

趕快加入我們來參與討論吧！

您需要登錄才可以下載或查看，沒有帳號？加入我們

x

有誰會解這題

執行時間1秒
為了方便起見，老師的計算方法是先將便當切成以1 cm × 1 cm 為單位的小格子，每個格子不
是阿力會吃就是阿力不會吃。對於阿力不吃的菜，老師假設阿力會挖掉的區域為不吃的食物所存
在的格子與其上下左右相連的格子，對於所有會被挖掉的區域，阿力會挖掉3 cm 厚的白飯。示意
圖如下，下圖是一個便當的表面，0 代表是阿力會吃的食物，1 代表是阿力不吃會挖掉的食物，灰
色區域就是阿力所有會挖掉的區域，總共是18 cm2 ，因此阿力總共會挖掉18 × 3 = 54 cm3 的白
飯。
阿力可以食用的白飯量即為白飯原本的體積減掉被挖掉的白飯體積。
因為市面上的便當琳瑯滿目，因此松板老師想請你幫忙寫個程式，協助計算各種便當小朋友可
食用的白飯量是多少。

輸入說明
輸入的第一行有一個正整數T(T 100)，代表測試資料的組數。
每一組測試資料的第一行有三個正整數M,N,K (3 M,N,K 50) 分別以空白隔開。M 代
表便當的長度，N 代表便當的寬度，K 代表便當的高度。
接下來會有M 行，每行有N 個數字，分別以一個空白隔開，表示便當表面每一格是否是阿力
會吃的食物。數字由0 與1 組成，0 代表是阿力會吃的食物，1 代表是阿力不吃會挖掉的食物。
輸出說明
對於每一筆測試資料請輸出一列，表示阿力可以食用的白飯量。

範例輸入
2
9 10 5
0 0 0 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0 1 1
5 5 3
0 0 0 0 0
0 1 1 0 0
0 0 0 1 1
0 0 0 0 1
0 0 1 0 0
範例輸出
336
21

我的程式碼
不知哪裡有錯
時間又超出限制

[C++] 純文本查看 復制代碼

#include<iostream>
using namespace std;
int main()
{
        int t=0,m=0,n=0,k=0;
        cin>>t;
        int ans[t-1];
        bool yes=true;
        bool no=false;
        for(int times=0,ans_e=0;times<t;times++,ans_e++)
        {
                cin>>m>>n>>k;
                int rice[m][n],g=0,h=0,i=0;
                for(int e=0;e<m;e++)
                {
                        for(int f=0;f<n;f++)
                        {
                                cin>>rice[e][f];
                        }
                }
                for(int e=0;e<m;e++)
                {
                        for(int f=0;f<n;f++)
                        {
                                if(rice[e][f] == 1)
                                {
                                        rice[e][f]=2;
                                        //cout<<"rice["<<e<<"]["<<f<<"]"<<endl;
                                        rice[e-1][f]=2;
                                        //cout<<"rice["<<e-1<<"]["<<f<<"]"<<endl;
                                        rice[e][f-1]=2;
                                        //cout<<"rice["<<e<<"]["<<f-1<<"]"<<endl;
                                        if(rice[e+1][f] != 1)
                                        {
                                                rice[e+1][f]=2;
                                                //cout<<"rice["<<e+1<<"]["<<f<<"]"<<endl;
                                        }
                                        if(rice[e][f+1] != 1)
                                        {
                                                //cout<<"rice["<<e<<"]["<<f+1<<"]"<<endl;
                                                rice[e][f+1]=2;
                                        }
                                        
                                        i=k-3;
                                        
                                }
                                else //if(rice[e][f] == 0 && rice[e][f] != no)
                                {
                                        rice[e][f]=0;
                                }
                        }
                }
                
                for(int e=0;e<m;e++)
                {
                        for(int f=0;f<n;f++)
                        {
                                if(rice[e][f]==2)
                                {
                                        h++;
                                }
                                else
                                {
                                        g=(m*n)-h;
                                }
                                //cout<<"rice["<<e<<"]["<<f<<"]"<<endl;
                                //cout<<"g="<<g<<endl;
                                //cout<<"h="<<h<<endl;
                        }
                        //cout<<endl;
                }
                //cout<<i<<endl;
                cout<<(g*k)<<endl;
                cout<<(i*h)<<endl;
                ans[ans_e]=(g*k)+(i*h);
                
        }
        
        for(int e=0;e<t;e++)
        {
                cout<<ans[e]<<endl;
        }
        
        return 0;
}

另外
"cin 輸入經測試發現速度遠慢於scanf 輸入"
這甚麼意思

By Sylveon
請取一個適當標題

Sylveon · 發表於 2014-8-25 14:25:29

cin為了與C語言的IO相容，所以預設上，cin會多做很多動作。假若你不用scanf的話，可以加上這兩行來關閉此功能達到提升速度的效果。
什麼都不做的狀況下，cin比scanf慢上2倍以上，尤其IO量很大的狀況下特別明顯。

[C++] 純文本查看 復制代碼

#include<iostream>
using namespace std;
int main()
{
	ios::sync_with_stdio(false);
	//下面三選一 
	cin.tie( NULL );
	//cin.tie( 0 );
	//cin.tie( nullptr ); //C++11 support
	int a;
	cin>>a;
	cout<<"in:"<<a<<endl;
}

參考資料：http://www.hankcs.com/program/cp ... put-and-output.html

Sylveon · 發表於 2014-8-25 14:29:59

陣列請用常數宣告，這些都不是標準的C++語法

#

cin>>t;

int ans[t-1];

cin>>m>>n>>k;

int rice[m][n];

林宇翔 · 發表於 2014-8-25 14:31:19

Sylveon 發表於 2014-8-25 14:25
cin為了與C語言的IO相容，所以預設上，cin會多做很多動作。假若你不用scanf的話，可以加上這兩行來關閉此功 ...

我不知道我的程式哪裡寫錯
輸出的答案都是錯的

Sylveon · 發表於 2014-8-25 14:33:56

林宇翔發表於 2014-8-25 14:31
我不知道我的程式哪裡寫錯
輸出的答案都是錯的

那你能分析你的程式碼如何運作嗎? 因為如果連自己的程式都不知造怎麼運行，寫出來的這個程式沒有意義

allenwhale · 發表於 2014-8-25 14:54:35

你的debug code有沒有拿乾淨?
用常數宣告的意思就是用數字或是有const的變數當作長度

[C++] 純文本查看 復制代碼

int s1[100];
const int N=100;
int s2[N];
#define MAXN 100
int s3[MAXN];

林宇翔 · 發表於 2014-8-25 15:01:44

本帖最後由林宇翔於 2014-8-25 15:07 編輯

Sylveon 發表於 2014-8-25 14:33
那你能分析你的程式碼如何運作嗎? 因為如果連自己的程式都不知造怎麼運行，寫出來的這個程式沒有意義 ...

我有加上註解
麻煩幫我看一下

[C++] 純文本查看 復制代碼

#include<iostream>
using namespace std;
int main()
{
        int t=0,m=0,n=0,k=0;//宣告變數 
        cin>>t;//讀入測資數量 
        int ans[t-1];
        for(int times=0,ans_e=0;times<t;times++,ans_e++)//多測資輸入 
        {
                cin>>m>>n>>k;//m代表y軸,n代表x軸,k代表z軸 
                int rice[m][n],g=0,h=0,i=0;
                for(int e=0;e<m;e++)//讀入測資 
                {
                        for(int f=0;f<n;f++)
                        {
                                cin>>rice[e][f];
                        }
                }
                for(int e=0;e<m;e++)//判斷是否為1,如果是1，將上下左右都編為2 
                {
                        for(int f=0;f<n;f++)
                        {
                                if(rice[e][f] == 1)
                                {
                                        rice[e][f]=2;
                                        //cout<<"rice["<<e<<"]["<<f<<"]"<<endl;
                                        rice[e-1][f]=2;
                                        //cout<<"rice["<<e-1<<"]["<<f<<"]"<<endl;
                                        rice[e][f-1]=2;
                                        //cout<<"rice["<<e<<"]["<<f-1<<"]"<<endl;
                                        if(rice[e+1][f] != 1)
                                        {
                                                rice[e+1][f]=2;
                                                //cout<<"rice["<<e+1<<"]["<<f<<"]"<<endl;
                                        }
                                        if(rice[e][f+1] != 1)
                                        {
                                                //cout<<"rice["<<e<<"]["<<f+1<<"]"<<endl;
                                                rice[e][f+1]=2;
                                        }
                                        
                                        i=k-3;
                                        
                                }
                                else //if(rice[e][f] == 0 && rice[e][f] != no)
                                {
                                        rice[e][f]=0;
                                }
                        }
                }
                
                for(int e=0;e<m;e++)//判斷有哪些是2 
                {
                        for(int f=0;f<n;f++)
                        {
                                if(rice[e][f]==2)
                                {
                                        h++;
                                }
                                else
                                {
                                        g=(m*n)-h;
                                }
                                //cout<<"rice["<<e<<"]["<<f<<"]"<<endl;
                                //cout<<"g="<<g<<endl;
                                //cout<<"h="<<h<<endl;
                        }
                        //cout<<endl;
                }
                //cout<<i<<endl;
                //cout<<(g*k)<<endl;
                //cout<<(i*h)<<endl;
                ans[ans_e]=(g*k)+(i*h);//將最後答案計算出來，儲存於陣列中
                
        }
        
        for(int e=0;e<t;e++)//顯示答案 
        {
                cout<<ans[e]<<endl;
        }
        
        return 0;
}

如何看程式執行時間

林宇翔 · 發表於 2014-8-25 15:20:36

allenwhale 發表於 2014-8-25 14:54
你的debug code有沒有拿乾淨?
用常數宣告的意思就是用數字或是有const的變數當作長度[mw_shl_code=cpp,true ...

一定要這樣做嗎?

林宇翔 · 發表於 2014-8-25 15:43:40

你的code充斥著超出陣列的問題

what?
甚麼意思

allenwhale · 發表於 2014-8-25 16:21:53

林宇翔發表於 2014-8-25 15:43
what?
甚麼意思

以你的code為例
當e=0,f=0時
不會存在rice[e-1][f] and rice[e][f-1] //rice[-1][0] and rice[0][-1]

[提問] npsc 2013試題 A. 挑食的大胃王

趕快加入我們來參與討論吧！

點評

點評

點評

程式設計達人 - 2014

新手達陣

台南一中資訊社