Kattis fontan

題目

https://open.kattis.com/problems/fontan

給一個 $N \times M$ 的圖，上面有 ., #, V 三種元素，分別表示 空氣、石頭、水

水可以每次從上往下流動一個單位，但是當往下會遇到石頭的時候水會往兩側移動

現在告訴你一開始哪裡有水，請輸出水不再流動時圖的情況

想法

水的擴散情形就跟地圖上 BFS 一樣，每次都是全部擴散出去一格

每次檢查是否可以往下走，如果可以就往下，如果不行就檢查兩側，直到沒有水可以再移動就輸出答案

Code

//By Koios1143
#include<iostream>
using namespace std;
int n, m, S=0, que[2550][2];
int dx[] = {0, 0};
int dy[] = {-1, 1};
char arr[55][55];
bool vis[55][55];

void BFS(){
	for(int i=0, j=S, x, y, nx, ny ; i<j ; i++){
		x = que[i][0];
		y = que[i][1];
		
		// 先檢查往下
		nx = x + 1;
		ny = y;
		if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
		if(!vis[nx][ny] && arr[nx][ny] == '.'){
			vis[nx][ny] = true;
			que[j][0] = nx;
			que[j][1] = ny;
			arr[nx][ny] = 'V';
			j++;
		}
		// 是石頭就再檢查左右
		else if(!vis[nx][ny] && arr[nx][ny] == '#'){
			for(int k=0 ; k<2 ; k++){
				nx = x + dx[k];
				ny = y + dy[k];
				if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
				if(!vis[nx][ny] && arr[nx][ny] == '.'){
					vis[nx][ny] = true;
					que[j][0] = nx;
					que[j][1] = ny;
					arr[nx][ny] = 'V';
					j++;
				}
			}
		}
	}
}

int main(){
	for(int i=0 ; i<55 ; i++){
		for(int j=0 ; j<55 ; j++){
			vis[i][j] = false;
		}
	}
	cin>>n>>m;
	for(int i=0 ; i<n ; i++){
		for(int j=0 ; j<m ; j++){
			cin>>arr[i][j];
			if(arr[i][j] == 'V'){
				que[S][0] = i;
				que[S][1] = j;
				vis[i][j] = true;
				S++;
			}
		}
	}
	BFS();
	for(int i=0 ; i<n ; i++){
		for(int j=0 ; j<m ; j++){
			cout<<arr[i][j];
		}
		cout<<"\n";
	}
	return 0;
}

時間複雜度分析

輸入時間複雜度為 $O(nm)$

BFS 時間複雜度為 狀態數 $\times$ 操作的數量 $= (nm) \times 3$ 計為 $O(nm)$

總時間複雜度為 $O(nm)$