接上一篇,好不容易擺脫掛蛋之後
本來應該開始解決阿業的數字組合
但阿業說他還需要一些時間,並把阿維抓了過去
於是我先開始解決我的老鼠走迷宮問題

Problem I
---------------------

輸入一個迷宮(迷宮大小<=100),裡面有若干的人(人數<=10)
每個人取走到出口最快的步數(假設走5步、10步、20步都能到出口,就算5步)
計算出走最慢的人減走最快的人步數的值
(設有三人最快步數為3步、5步、10步,就輸出7)

範例輸入會告訴你有幾個迷宮,長寬為何,共有幾人
最後輸入迷宮的圖
W代表牆,B是道路,S是人(也算道路),E是出口

Time Limit:5 sec.

Sample Input
2
9 10 3
WWWWWWWWWW
EBBBWWBBBE
WWSWBWSWWW
WWBWBWWBBE
WWBWSWWBWW
WWBWBWWBWW
WWBWBBBBBB
WWBBBBWWWB
WBWWWWWBBB
7 6 2
WWWEWW
WWWBWW
WWWBWW
WWBBBB
WWSWWB
WWBBBS
WWWWWW


Output for the Sample Input
7 <<10-3
2 <<7-5


這題你有什麼想法呢?其實就是很簡單的老鼠走迷宮而已
但老實說我是第一次寫老鼠走迷宮
能不能寫出來,我真的沒把握
而且我一直搞不懂rows跟cols的關係
到底對電腦來說哪個是直的哪個是橫的

總之,開始寫了,寫的途中其實小問題不斷
像是打錯字啦,少一個括號啦
多虧阿業與阿維在旁邊有提醒我才能正常編譯
可是...編譯結果,竟然是錯的??
於是我把每一步給顯示出來,看看到底是怎麼回事
查出來的原因讓我噴飯,竟然是因為...我打錯輸入檔了orz

可是我更改之後發現顯示還是為0
再度檢查發現因為最少步數預設值為0
但我的程式有設定步數較少才更新記錄
而只要有迷宮都不可以比0步還要少
才會造成最小值永遠為0的情況

為了找這幾個bug,已經花了一個小時了
但困難的現在才開始
打上第二筆測試資料後,竟然視若無睹?
那是因為當時只測試一筆資料,我的Sample Input為1還沒改
改完後卻發現第二筆資料答案錯誤!
長寬人數都讀的莫名其妙,但程式明明就找不到問題
又這樣耗費了一個小時後,我最後才想到該不會是我的長寬讀錯了吧
試了一下差點沒吐血,還真的如此>__<
對不起組員,寫程式只花了半小時,找bug至少浪費兩個多小時

總之測試結果是對了,我們便歡天喜地的寄出答案
你知道他回傳了什麼嗎?竟然是Over time limit!
誰能告訴我這是怎樣?在電腦上跑的時間明明才顯示0.001秒
老鼠走迷宮不就是這樣寫的嗎?
而且我又不是華盛頓,實在找不到地方砍樹
由於迷宮的出口不只一個,又不能找到出口後就不做了
到底要怎麼樣才能減少執行時間呢?

沒有辦法,我把清除資料的部份改的好一點
只清除有動到過的陣列內容,希望能稍微減少一點時間
而且阿業也說以前柯國偉學長曾經發生第一次超時,第二次寄竟然通過的案例
但這種好運並沒有發生在我身上,第二次還是超時
(每傳錯誤答案一次會給予20分鐘的懲罰時間,名次會往後掉)

時間只剩下5分鐘了,題數還是一題
雖然當初就打算只是來玩玩的,但這種成績以後會沒臉見人
於是我最後減少兩個判斷式來孤注一擲
結果還是超時了||orz
此時宣告死刑的鈴聲響起,比賽在5:30結束了

至於阿業呢,因為他想不到組合的程式碼
再加上時間也不夠了,所以他們兩位就來支援我啦
太可惜了,我當初就有看過組合的程式碼
可是當時卻沒有存起來跟印下來
想不到半年以後卻因此栽在這題手上

現在放棄的話,比賽就結束了
我沒有放棄,可是比賽還是結束了

最後問了大家的戰績
阿良那組也是一題,他們有一題一直顯示error
但是卻找不到問題所在
而那一題,正好是我們唯一解出來的那題
學弟妹兩組則都是掛蛋
雖然我們的結果很差,但本來就不抱得獎的希望
所以也沒什麼好失望的
只是因為超時而沒有答對那題,讓我覺得很可惜

當晚跟深思聊天後,打題目到一半我才終於了解該怎麼砍樹
由於題目只要求最快步數
只要目前走的步數>=最快步數,那麼以下的樹就可以全砍了
因為再怎麼走都不會比較快了
為什麼我當時沒有想到這步呢?
果然是因為沒有練習而太慌了吧

不過這次的大甲比賽辦的不算很好
這次題目一直做修正,至少改了3題題目
還有雖然他跟ACM一樣外面擺了小點心,但我們哪有時間去吃啊
而阿維出去後才發現小點心早就光了
主辦單位擺的量也太少了吧,是在響應節能減碳嗎?

以結果論而已,我們這次表現的很不好
但其實我們從頭到尾也只看了這三題而已
也許其他的題目比較簡單,但也沒時間慢慢看了
除非實力夠強,否則運氣成分其實佔了大多數
這次的失敗,激起了我下個月參加ACM的意願
希望這一年來的焠鍊,能讓我的程式設計更上一層樓

蕭雲 發表在 痞客邦 PIXNET 留言(0) 人氣()