2558 問題 C: 藍(lán)橋杯2019年第十屆國賽真題-估計人數(shù)
時間限制: 1s
內(nèi)存限制: 128MB 提交: 249 解決: 31
題目描述
給定一個 N × M 的方格矩陣,矩陣中每個方格標(biāo)記 0 或者 1 代表這個方格是不是有人踩過。
已知一個人可能從任意方格開始,之后每一步只能向右或者向下走一格。走了若干步之后,這個人可以離開矩陣。這個人經(jīng)過的方格都會被標(biāo)記為 1,包括開始和結(jié)束的方格。注意開始和結(jié)束的方格不需要一定在矩陣邊緣。請你計算至少有多少人在矩陣上走過。
輸入
輸入第一行包含兩個整數(shù) N、M。
以下 N 行每行包含 M 個整數(shù) (0/1),代表方格矩陣。
樣例輸入
5 5
00100
11111
00100
11111
00100