Kattis Conquest Campaign

題目

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

給一張 $R \times C$ 的地圖，其中有 $N$ 個可重複的點，標示我們的起點

圖上沒有任何障礙物，在這至多 $N$ 個起點每天我們可以往上下左右四個方向擴散，請問最少幾天可以把全部地圖佔領

想法

因為要球最少步驟，所以想到用 BFS 來實作

會影響到未來發展的只有我們佔據了哪些點，所以狀態只需要紀錄被佔領的點座標即可

接下來每次向外四個方向擴散

要注意的是，起點可能重複給，但是實際上重複是沒有意義的

並且為了方便確定當前是不是全部的點都佔領了，我們透過確認當前總共有多少座標被標記在 BFS 的序列當中，那麼重複的點就不應該被重複計算，所以要先拔除

Code

//By Koios1143
#include<iostream>
using namespace std;
int R, C, N, S, que[10005][2], dis[105][105];
int dx[] = {-1, 0, 0, 1};
int dy[] = {0, -1, 1, 0};
bool vis[105][105];

void print_all(){
	for(int i=1 ; i<=R ; i++){
		for(int j=1 ; j<=C ; j++){
			if(vis[i][j]) cout<<"*";
			else cout<<'.';
		}
		cout<<"\n";
	}
	cout<<"\n";
}

int BFS(){
	for(int i=0, j=S, x, y, nx, ny ; i<j ; i++){
		x = que[i][0];
		y = que[i][1];
		if(j == R*C){
			// 檢查是否已經佔領所有點
			return dis[que[j-1][0]][que[j-1][1]];
		}
		for(int k=0 ; k<4 ; k++){
			nx = x + dx[k];
			ny = y + dy[k];
			if(nx <= 0 || nx > R || ny <= 0 || ny > C) continue;
			if(!vis[nx][ny]){
				vis[nx][ny] = true;
				dis[nx][ny] = dis[x][y] + 1;
				que[j][0] = nx;
				que[j][1] = ny;
				j++;
			}
		}
	}
	return -1;
}

int main(){
	for(int i=0 ; i<105 ; i++){
		for(int j=0 ; j<105 ; j++){
			vis[i][j] = false;
		}
	}
	cin>>R>>C>>N;
	S=0; // 紀錄不重複的起點數量
	for(int i=0, x, y ; i<N ; i++){
		cin>>x>>y;
		if(!vis[x][y]){
			que[S][0] = x;
			que[S][1] = y;
			vis[x][y] = true;
			dis[x][y] = 1;
			S++;
		}
	}
	cout<<BFS()<<"\n";
	return 0;
}

時間複雜度分析

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

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

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

Koios1143的筆記

Kattis - Conquest Campaign

Kattis Conquest Campaign

題目

想法

Code

時間複雜度分析