# **Zerojudge d406 倒水時間**

:::warning
題目:
水由上而下的流，現在給你水管之間的地圖
水可以由上而下，可以往右流，往左流。
可是呢 ... 有時候也可以往上流
現在從地圖的最上方開始倒水，請輸出到的時間，水不能走的地方輸出0。
※ 開始倒的地方只有 1 個且只在第一列倒。

每組測資的第一列有一個數字 S，若 S = 2 代表水不能往上流， S = 1 代表水可以往上流。
第二列有兩個數字 N M， N 代表接下來有 N 列，M代表每列上有多少數字。( 1≦ N M ≦ 100 )
接下來會有 N 列，每列上有 M 個數字， 1 代表有水管， 0 則代表沒有。
https://zerojudge.tw/ShowProblem?problemid=d406
:::

這題是經典的 ==BFS(廣度優先搜尋法)的題目==，但是多加了不能向上的限制
***
首先引入bfs必要的queue、pair陣列的標頭檔

#include<iostream>  
#include<queue>  //queue
#include<utility> //pair

***
宣告題目需要的變數(全域變數，部分變數用意之後會提)

int first_1, s, n, m, arr[1000][1000], ans[1000][1000], dx[4] = {1,-1,0,0}, dy[4] = {0,0,1,-1}; 
bool visited[1000][1000] = {0};

***
輸入

cin >> s;
cin >> n >> m;
for(int i=0 ; i<n ; i++)
for(int j=0 ; j<m ; j++)
{
	cin >> arr[i][j]; //輸入
	if(i == 0 && arr[i][j] == 1)  //找到起點
	first_1 = j;
}

因為題目說 ==開始倒的地方只有 1 個且只在第一列倒==，所以我們在輸入第一列時( i=0 )便找出倒水的起點( j )
***
輸入完開始bfs，我習慣把bfs寫成函式，這也是為什麼我是宣告全域變數的原因，如果是在int main宣告那這樣只是**區域變數**，int main外的函式無法使用

bfs(); //呼叫函式

void bfs()
{
	queue<pair<int,int>> q; //首先宣告一個用pair的queue陣列
	visited[0][first_1] = 1; //visited記錄這個點有沒有被走過(有就設為1)
	ans[0][first_1] = 1;//(ans陣列用來紀錄時間點)
	q.push(make_pair(0,first_1));//把0,first也就是起點丟進queue陣列裡
	while(q.size()!=0)
	{
		pair<int,int> p = q.front();
		q.pop();
		for(int i=0 ; i<4 ; i++)
		{
			if(s == 2 && i == 1) continue; //x+dx[1] 為向上走故跳過
			int nx = p.first + dx[i], ny = p.second + dy[i];
			
			if(nx < 0||ny < 0||nx >= n||ny >= m) continue;
			
			if(arr[nx][ny] == 1 && visited[nx][ny] == 0) //若這個點為1(水管)且沒被走過
			{
				q.push(make_pair(nx,ny));//將這個點丟進queue陣列
				visited[nx][ny] = 1;//將這個點設定為已走過
				ans[nx][ny] = ans[p.first][p.second]  + 1;
			}
		}
	}
	return;
}

用**pair**可以方便存取
而dx[4] = {1,-1,0,0}, dy[4] = {0,0,1,-1}是變量
可以直接用for迴圈重複4次就可以有上下左右4個點了

至於22行的部分為何是**ans[nx][ny] = ans[p.first][p.second] + 1**，==**因為現在這一格是前一格的下一個時間點所以加1**== (起點為1，下一個為水管且還未被走過就是2，以此類推)，這樣最後輸出就可以知道每格的時間點了
***
輸出

for(int i=0 ; i<n ; i++)
	{
	if(i>0) cout << "\n";//換行用
		for(int j=0 ; j<m ; j++)
		j < m-1 ? cout << ans[i][j] << " " : cout << ans[i][j]; 
	}

第五行是讓輸出時每行結尾沒有空格

題目有說**水不能走的地方輸出0**，但因為我們的 ==ans陣列是全域變數即**預設為0**==，所以牆壁和走不到的地方不會被動到，也就是0了
***
最後把重複輸入的條件加上去就好了
:::success
完整程式碼
:::

#include<iostream>
#include<queue>
#include<utility>
using namespace std;
int Case = 1, first_1, s, n, m, arr[1000][1000], ans[1000][1000], dx[4] = {1,-1,0,0}, dy[4] = {0,0,1,-1}; 
bool visited[1000][1000] = {0};
void bfs()
{
	queue<pair<int,int>> q;
	visited[0][first_1] = 1;
	ans[0][first_1] = 1;
	q.push(make_pair(0,first_1));
	while(q.size()!=0)
	{
		pair<int,int> p = q.front();
		q.pop();
		for(int i=0 ; i<4 ; i++)
		{
			if(s == 2 && i == 1) continue;
			int nx = p.first + dx[i], ny = p.second + dy[i];
			
			if(nx < 0||ny < 0||nx >= n||ny >= m) continue;
			
			if(arr[nx][ny] == 1 && visited[nx][ny] == 0)
			{
				q.push(make_pair(nx,ny));
				visited[nx][ny] = 1;
				ans[nx][ny] = ans[p.first][p.second]  + 1;
			}
		}
	}
	return;
}
int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	while(cin>>s)
	{
		cin >> n >> m;
		for(int i=0 ; i<n ; i++)
		for(int j=0 ; j<m ; j++)
		{
			cin >> arr[i][j]; 
			if(i == 0 && arr[i][j] == 1)  
			first_1 = j;
		}
        
		bfs();
		
		cout << "Case " << Case << ":\n"; 
		for(int i=0 ; i<n ; i++)
		{
		if(i>0) cout << "\n";
			for(int j=0 ; j<m ; j++)
			j < m-1 ? cout << ans[i][j] << " " : cout << ans[i][j]; 
		}
		cout << "\n";
		
		Case++;
		for(int i = 0 ; i < 1000 ; i++)
		for(int j = 0 ; j < 1000 ; j++)
		{
			arr[i][j] = 0; 
                       ans[i][j] = 0; 
                       visited[i][j] = 0;
		}
	}
	return 0;
}

:::success
掰掰 :D
:::