# d406: 倒水時間
題目連結：[d406](https://zerojudge.tw/ShowProblem?problemid=d406)
這題比較適合BFS
因為水流的是一樣的時間

我的作法是找到一個點
將它附近的點放進Queue裡
再從Queue裡pop出點來
再將pop出來附近的點放進Queue裡
如此模擬水流

那將經過的點標上做了幾次模擬的次數即為解

以下為程式碼：

#include<stdio.h>
#include<queue>
#include<iostream>
#include<utility>
using namespace std;

int dx[] = {1, 0, 0, -1};
int dy[] = {0, -1, 1, 0};

 int main(){
 	int marked[100][100];
 	int arr[100][100];
 	int x,y,i,j,r,c,s,nr,nc,o=1;
 	while(scanf("%d%d%d",&s,&x,&y)!=EOF){
 		int marked[100][100]={0};
 		for(i=0;i<x;i++){
 			for(j=0;j<y;j++){
 				scanf("%d",&arr[i][j]);
 				if(i==0&&arr[i][j]==1){
 					r=i;
 					c=j;
				 }
			 }
		}
		queue< pair<int,int> > q;
		q.push({r,c});
		marked[r][c]=1;
		while(!q.empty()){
			r = q.front().first;
                       c = q.front().second;
                       q.pop();
                       for(i=0;i<5-s;i++){
                          	nr=r+dx[i];
                        	nc=c+dy[i];
                        	if(nr<0||nc<0||nr>=x||nc>=y){
            	        	continue;
                        }
                        if(arr[nr][nc]==0){
                               continue;
                        }
                        if(marked[nr][nc]>0){
                                continue;
                        }
                        marked[nr][nc]=marked[r][c]+1;
                        q.push({nr,nc});
                }
		}
		printf("Case %d:\n",o);
		o++;
		for(i=0;i<x;i++){
 			for(j=0;j<y;j++){
 				printf("%d ",marked[i][j]);
			}
			printf("\n");
		}
	 }
	 return 0;
 }

以下就是模擬水流的迴圈
當Queue為空時就是已經流到終點的了

while(!q.empty()){
	    r = q.front().first;
           c = q.front().second;
            q.pop();
            for(i=0;i<5-s;i++){
            	nr=r+dx[i];
            	nc=c+dy[i];
            	if(nr<0||nc<0||nr>=x||nc>=y){
            		continue;
				}
				if(arr[nr][nc]==0){
					continue;
				}
				if(marked[nr][nc]>0){
					continue;
				}
				marked[nr][nc]=marked[r][c]+1;
				q.push({nr,nc});
			}
		}