2019北理工計算機夏令營機試
今年北理工計算機夏令營一共兩道機試題，上機環(huán)境為dev c++稚瘾，支持STL和C++11计呈。測試為黑盒測試，即老師給你一張紙雨席，每個題輸入上面的樣例菩咨，三個都過了就是滿分。今年機試題分為兩組進行陡厘，難度較往年來說有所加大抽米，區(qū)分度高了一些，以下是第二組的題目及思路糙置。
第一題
題目：給你一個m*n大小的矩陣云茸，每個點有0，1谤饭，2三種取值标捺；0代表障礙物懊纳，1代表白紙，2代表墨滴亡容。每一秒墨滴可以向其上下左右擴散嗤疯，將四周的白紙染色，被染色之后的白紙可以繼續(xù)向四周擴散闺兢，以此類推茂缚。問經(jīng)過幾秒，矩陣中所有的白紙都被染色屋谭，如果可以脚囊，則輸出擴散時間；如果不可以桐磁，則輸出FALSE悔耘。
輸入： m n 的大小以及矩陣每個點的值
輸出：擴散時間 或 FALSE
例如：
3 3 ? ? ? ? ? ? ? ? ? ?3 3 ? ? ? ? ? ? ? ? ? ?2 3
0 1 0 ? ? ? ? ? ? ? ? 0 1 0 ? ? ? ? ? ? ? ? 1 0 0
1 2 1 ? ? ? ? ? ? ? ? ?1 2 1 ? ? ? ? ? ? ? ? 0 0 2?
0 1 0 ? ? ? ? ? ? ? ? 0 1 1 ? ? ? ? ? ? ? ? 輸出：FALSE
輸出：1 ? ? ? ? ? ?輸出：2
個人思路：這道題感覺和leetcode上“腐爛的橘子”一題很像，首先需要找到初始狀態(tài)下所有值為2的點（注意：值為2的點在一開始可能不僅僅為1個）所意，然后再設一個隊列淮逊，利用BFS求解即可。
第二題
題目：輸入三個字符串扶踊，問第三個字符串能否由前兩個字符串多次重復組合形成泄鹏。如果能，則輸出前兩個字符串各自的使用次數(shù)秧耗；如果不能备籽，則輸出FALSE。
輸入：三個字符串
輸出：前兩個字符串各自的次數(shù) 或 FALSE
例如：
aa bb bbaaaabbaa
輸出：3 2
ab ba abbaaabaab
輸出：FALSE
個人思路：乍一看感覺這個題挺簡單分井，從頭開始车猬，挨個往后匹配就可以了，也就是先匹配第一個尺锚，如果可以珠闰，就去找當前位置加上第一個字符串長度的地方繼續(xù)匹配，第一個不成功再去匹配第二個瘫辩。但是仔細想想有這么一種情況伏嗜，例如第一個字符串為aa，第二個字符串為aab伐厌，第三個字符串為aabaa承绸，這種輸入是可以匹配成功的，但用上述方法顯然會輸出FALSE挣轨。因此本題我才用的思路是用DFS+回溯军熏，即在同一個位置上讓兩個模式串都去試著匹配一下，在匹配到尾部的時候返回即可卷扮。
總結
今年北理機試題較往年來說難度有所增加荡澎，兩道題一道BFS均践，一道DFS，但也不是太難摩幔，基本都是板子題浊猾，多刷刷leetcode還是很有用的。
如有疑問热鞍，歡迎大家一起交流～
