【題目鏈接】

ybt 1191：流感傳染
OpenJudge NOI 2.3 6262:流感傳染

【題目考點】

1. 二維數組

2. 隊列

【解題思路】

用一個字符型二維數組存儲各個房間的情況。

1. 多趟遍歷二維數組

每一天遍歷整個二維數組，如果當前房間有健康的人'.'，而周圍房間前一天有患病的人'@'，那么當前房間的人在這一天也會患病。
更新過程中，可以設臨時數組保存新的一天的情況，然后再拷貝給原數組。
循環16次，而后統計整個二維數組中患病的人數。
每天都要遍歷二維數組，二維數組為n*n，共m天，該算法復雜度為$O(m?n^2)$
m最大100，n最大為100，最大運算次數達到$10^6$數量級，是可行的。

2. 隊列優化

這一過程有點類似于廣搜。
由于一個患病的人第一天已經將周圍的人傳染，第二天及以后周圍的都是患病的人，也就無法再傳染給更多的人。只有前一天剛剛被傳染的人，在下一天才會傳染給別人。
設結構體，保存一個人所在的位置，以及他是第幾天被感染的。
設隊列保存剛剛患病的人，隊列中保存的是上述該結構體類型的對象。
只要隊列不空，每次出隊一人u，將u周圍的人感染，這些人感染被感染的日子是u被感染的日子加1。如果u是第m天被感染的，則不再向外傳染。統計出隊的元素的個數，即為前m天被感染的人數。
該算法中每個患病的人至多遍歷1次，運算復雜度為$O(n^2)$，最大運算次數達到$10^4$數量級，優于解法1。

題外話：如果學過圖論算法，這兩種算法間的關系類似于Bellman-ford算法與SPFA算法之間的關系。

【題解代碼】

解法1：多趟遍歷二維數組

#include <bits/stdc++.h> using namespace std; #define N 105 int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}}; int main() {char mp[N][N], t[N][N];//t:臨時數組 int n, m, ct = 0;cin >> n;for(int i = 1; i <= n; ++i)for(int j = 1; j <= n; ++j)cin >> mp[i][j];cin >> m;for(int k = 2; k <= m; ++k)//第k天如何傳染 {memset(t, 0, sizeof(t));//對t清空。 for(int i = 1; i <= n; ++i)for(int j = 1; j <= n; ++j){t[i][j] = mp[i][j];if(mp[i][j] == '.')//如果(i,j)沒患病，但周圍有病人，就會被傳染，否則和原來一樣。 {for(int l = 0; l < 4; ++l){int x = i + dir[l][0], y = j + dir[l][1];if(x >= 1 && x <= n && y >= 1 && y <= n && mp[x][y] == '@') t[i][j] = '@';}}}memcpy(mp, t, sizeof(t));//拷貝t到mp }for(int i = 1; i <= n; ++i)for(int j = 1; j <= n; ++j)if(mp[i][j] == '@')ct++;cout << ct; return 0; }

解法2：隊列優化

該解法使用scanf讀入字符型二維數組，因為scanf("%c")會讀入換行符，因而要注意吸收換行符。

#include <bits/stdc++.h> using namespace std; #define N 105 struct Node {int x, y, d;//x，y：坐標 d：天數Node(){}Node(int a, int b, int c):x(a),y(b),d(c){} }; char mp[N][N]; bool vis[N][N];//第i,j位置是否已經被統計過 int n, m, ct;//ct:計數 int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; queue<Node> que;//隊列 保存剛剛感染的人 int main() {scanf("%d\n", &n);//如不吸收本行的換行符，這個換行符會被下面的scanf("%c")讀入 for(int i = 1; i <= n; ++i){for(int j = 1; j <= n; ++j){scanf("%c", &mp[i][j]);if(mp[i][j] == '@'){que.push(Node(i, j, 1));//感染者入隊vis[i][j] = true;ct++;}}getchar();//注意，scanf("%c")會讀入換行符。這里需要用getchar()吸收每行末尾的換行符 }scanf("%d", &m);while(que.empty() == false){Node u = que.front();que.pop();if(u.d == m)//這是個第m天患病的人，不再統計m+1天被傳染的人 continue;for(int i = 0; i < 4; ++i){int x = u.x + dir[i][0], y = u.y + dir[i][1], d = u.d + 1;if(x >= 1 && x <= n && y >= 1 && y <= n && vis[x][y] == false && mp[x][y] == '.'){que.push(Node(x, y, d));vis[x][y] = true;ct++;}}}printf("%d", ct);return 0; }

總結

以上是生活随笔為你收集整理的信息学奥赛一本通 1191：流感传染 | OpenJudge NOI 2.3 6262:流感传染的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。