原題目簡述如下: 以 m x n 大小的 grid 代表一張地圖,現今要在此地圖內探勘,找出油田。某一區塊如果標示 "@" 代表有油,"*" 代表沒有油。 "@" 相鄰的區域的聯集,可視為一個油田。(所謂相鄰,除了上下左右,斜向的相鄰也算進去) 求任意地圖中,油田的個數。 例如輸入的測資為: * * * * @ * @ @ * @ * @ * * @ @ @ @ * @ @ @ * * @ 則油田個數為 2。 想法 採用典型的倒水演算法(Flood Fill),走訪 "@" 出現的區域,從此往下倒水,倒過水的區域標上 id,因此透過 id 的編號,可以得知油田的個數。 實作 先實作倒水演算法的子函式: void floodfill(vector<vector<char> >& map, vector<vector<int> >& id_table, int row, int col, int id) { if(row < 0 || (row >= map.size()) ) return; if(col < 0 || (col >= map[0].size())) return; if(map[row][col] != '@' || id_table[row][col] > 0) return; id_table[row][col] = id; floodfill(map, id_table, row-1, col-1, id); floodfill(map, id_table, row-1, col, id); floodfill(map, id_table, row-1, col+1, id); floodfill(map, id_table, row, col-1, id); floodfill(map, id_table, row, col+1,
留言
張貼留言