10096. Fast Game of Life (OpenCL)

I'm a slow walker, but I never walk backwards.

題目描述

生命遊戲中,對於任意細胞,規則如下: 每個細胞有兩種狀態-存活或死亡,每個細胞與以自身為中心的周圍八格細胞產生互動。

  • 當前細胞為存活狀態時,當周圍低於 2 個 (不包含 2 個) 存活細胞時,該細胞變成死亡狀態。
  • 當前細胞為存活狀態時,當周圍有 2 個或 3 個存活細胞時, 該細胞保持原樣。
  • 當前細胞為存活狀態時,當周圍有 3 個以上的存活細胞時,該細胞變成死亡狀態。
  • 當前細胞為死亡狀態時,當周圍有 3 個存活細胞時,該細胞變成存活狀態。

可以把最初的細胞結構定義為種子,當所有在種子中的細胞同時被以上規則處理後,可以得到第一代細胞圖。按規則繼續處理當前的細胞圖,可以得到下一代的細胞圖,周而復始。

輸入格式

輸入第一行有兩個整數 $N$, $M$,表示盤面大小為 $N \times N$,模擬週期次數 $M$。接下來會有 $N$ 行,每一行上會有 $N$ 個字符,以 0 表示 $(i, j)$ 格子上的細胞屬於死亡狀態,反之 1 為存活狀態。

  • $1 \le N \le 2000$
  • $0 \le M \le 5000$

輸出格式

對於每一組測資輸出 $N$ 行,每一行上有 $N$ 個字元表示模擬 $M$ 次的最終盤面結果。

範例輸入 1

5 1
10001
00100
01110
00100
01010

範例輸出 1

00000
00100
01010
00000
00100

範例輸入 2

5 3
10001
00100
01110
00100
01010

範例輸出 2

00000
00000
01110
00000
00000

編譯參數

$ gcc -std=c99 -O2 main.c -lOpenCL -fopenmp -o main
$ ./main

備註

  • 2016/05/07 放寬時間限制,請減少 clCreateBuffer 數量並重複使用那些已經建立好的。
  • 2016/05/09 提供測資下載
  • 2022/05 建議設定MAXGPU為1,第三張GPU偶爾會讓系統當機

by Morris

Discussion