アルゴリズム練習ノート(二)

同じ配列の練習
今回はMediumの難易度を試してみました
先周完成したテーマをずっと忘れて出しました==
タイトルアドレス:https://leetcode.com/problems/game-of-life/
テーマ:Game of Life
分類:Array
難易度:Medium
タイトルの説明:
According to the Wikipedia's article: "The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970."
ウィキペディアによると、生存ゲームは1970年にイギリスの数学者John Horton Conwayによって発明された自動式化された細胞ゲームである.
Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):
m*n個の細胞が広がる培養プレートをあげます.各細胞には初期の状態の生(1)または死(0)があり、各細胞の周囲には8つの方向の隣人(水平、垂直、対角)があり、ゲームでは以下の4つのルールに従っています.

Any live cell with fewer than two live neighbors dies, as if caused by under-population.

Any live cell with two or three live neighbors lives on to the next generation.

Any live cell with more than three live neighbors dies, as if by over-population..

Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

人口の衰退のため、生存する細胞の周りが2人の隣人より少ないと死んでしまう.
2人または3人の隣人が生存する細胞が次のラウンドまで生存する場合.
人口が膨張するため、生存する細胞の周りが3人以上の隣人が生存すれば死ぬ.
死んだ細胞の周囲に存在し、ちょうど3人の生存者しか存在しない隣人は、次の分裂で復活する.
Write a function to compute the next state (after one update) of the board given its current state.
前のラウンドに基づいて次のラウンドの各細胞の生存状態を計算するために方程式を記述する必要がある.
Follow up: 

Could you solve it in-place? Remember that the board needs to be updated at the same time: You cannot update some cells first and then use their updated values to update other cells.

In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches the border of the array. How would you address these problems?

分析:
上のテーマの説明からも分かるように、細胞の存在状態は2種類に分けられ、生(1)または死(0)である.
生存細胞は周囲に2人または3人の隣人が生存してこそ生存を続けることができる(1)、そうでなければ滅亡(0)
死の細胞は周囲に3人の生存する隣人がいれば(1)、そうでなければ滅亡する(0)
4つの状態(1−>1隣接=2 or 3;1−>0隣接>3 or<2;0−>1隣接=3;0−>0隣接≠3)
そこですべてが明らかになり,この2次元配列に対しては,それ自体の状態(0 or 1)を判断し,状態のカウントを行うだけでよい.
しかし、最終的には元の配列を覆うことが要求されるため、新しい配列を無駄にしたくない場合、すでに変化した細胞がその周囲に変化していない細胞に影響を及ぼすことは避けられない.
そこで,特殊な数字で次のラウンドの状態を表すとともに,その前のラウンドの状態(棒)も判断できると考える.
したがって,4つの状態のうち,変化した2つの状態(1−>0&0−>1)を数字−1と2で表す.
最終コードは次のとおりです.

class Solution {
public:
    void gameOfLife(vector>& board) {
        int m,n;
        n = board[0].size();
        m = board.size();
    	for(int x = 0; x < m; x++){
    		for(int y = 0; y < n; y++){
    			int count = 0, flag = 0;
    			if(board[x][y] == 0){
    			    for(int i1 = max(x - 1, 0); i1 < min(x + 2, m); i1++ ){
    			        for(int i2 = max(y - 1, 0); i2 < min(y + 2, n); i2++){
    			            if(i1 == x && i2 == y)continue;
    			            if(board[i1][i2] == 1 || board[i1][i2] == -1)
    			            count ++;
    			        }
        			}
        			if(count == 3)board[x][y] = 2;
    			}
    			else if(board[x][y] == 1){
    			    for(int i1 = max(x - 1, 0); i1 < min(x + 2, m); i1++ ){
    			        for(int i2 = max(y - 1, 0); i2 < min(y + 2, n); i2++){
    			            if(i1 == x && i2 == y)continue;
    			            if(board[i1][i2] == 1 || board[i1][i2] == -1)
    			            count ++;
    			            if(count > 3){
    			                board[x][y] = -1;
    			                flag = 1;
    			            }
    			        }
    			        if(flag == 1)break;
        			}
        			if(count < 2)board[x][y] = -1;
    			}
    			
    		}
    	}
    	for(int x = 0; x < m; x++){
    		for(int y = 0; y < n; y++){
    			if(board[x][y] == 2)board[x][y] = 1;
    			if(board[x][y] == -1)board[x][y] = 0;
    		}
    	}
    			
    }
};

もちろんネット上では、1人1人を左に移動し、最後にすべてを右に移動する方法もあります.上のコードよりも確かに速度が速くなります.
でもコードを打つとか、楽しければいいのに:-D