紅茶問題
發布時間: July 10, 2022, 2:56 p.m. 最後更新時間: Nov. 19, 2024, 6:03 p.m. 時間限制: 1000ms 記憶體限制: 128M
不吃午餐的YHY最近迷上了學校附近快餐店，一問之下才知他喜歡的是店裡提供的紅茶。有天，當YHY興高采烈地去裝紅茶時，一個不注意紅茶自己漏了出來。YHY和一同去用餐的同學們七手八腳地拿拖把阻止紅茶流動，畢竟如果被老闆娘發現的話是會被罵得很慘的！
由於紅茶事件發生時Noter沒有在現場，因此你決定用電腦程式幫助Noter了解當時的狀況。
你將現場的地圖切割成$N \times M$的矩形，$1$代表灑紅茶的起始點，$-1$代表紅茶不可流經之處（拖把所在地），$0$代表紅茶可流經之處。第一秒時紅茶在起點處，接下來紅茶會以每秒$1$單位座標的速率向上、下、左、右四個方向擴散，如果遇到流到拖把就會留在拖把處停止擴散（你可以把它視為障礙物，紅茶必須要繞過去）
第一行有兩個數$N, M$代表矩形的列數與行數（$1 \leq N, M \leq 1000, N, M \in \mathbb{N}$）
接下來有$N$列，每列有$M$個數$R_1, R_2, … , R_m$代表每個座標的情況（$R_i \in \{-1, 0, 1\}$）
在接下來有$Q$列分別代表$Q$筆詢問，每列有兩數$R_i, C_i$代表的第$R$列與第$C$行（$1 \leq Q \leq 10^4, 0 \leq R < N, 0 \leq C < M , Q, R, C \in \mathbb{N}$）
對於每筆詢問$R_i, C_i$，輸出該點在第幾秒時被紅茶淹到，如果不會被淹到輸出$0$，如果那裡是拖把輸出$-1$，（$0 \leq R_i < N, 0 \leq C_i < M$）。
3 2 -1 0 0 0 1 0 1 1 1 0 2 0
3 2 1
6 6 0 0 0 0 0 0 0 0 0 0 -1 0 0 -1 1 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 3 2 4
1 2 3
5 7 1 0 -1 0 -1 0 0 0 0 0 -1 0 -1 0 0 -1 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 -1 0 0 2 2 4 6 0 3 1 6 3 5 3 0 4 1
5 11 0 12 9 4 6
