在棋盤上發現方格可以被車攻擊

Question

問題是這樣的..

有一個NxN棋盤。棋盤上的每個方格可以是空的，也可以是白嘴鴉。我們知道的一隻白嘴鴉可以水平或垂直攻擊。給定一個二維矩陣，其中0代表一個空的正方形，1代表一個白嘴鴉，我們必須填寫矩陣中的所有單元格，其中1代表棋盤上存在的任何車子可以攻擊的正方形。

現在，我可以在O（n^3）時間和恆定的空間複雜度下輕鬆完成這個任務。然後在O（n^2）時間和O（2 * n）空間複雜度。但我需要找出O（n^2）時間和恆定空間的解決方案。有人請幫忙。

Answer 1

假設你知道，所有的烏鴉要麼在第一列或第一排。然後，通過遍歷第一行/列，並在每次看到一個白嘴鴉時填充矩陣（除了填充第一行/第一列，您在第一行/第一列中處理的內容），您將擁有一個沒有空間開銷的O（n^2）最後一步）。 如果所有的車都在最後一列/最後一行，第一列/最後一行，以及最後一列/第一行，這同樣成立。

現在把你的初始矩陣和迭代它，直到它包含一個車。讓我成爲這個車的排的索引，並且j是它的列的索引。繼續遍歷矩陣和你在位置（i'，j'）找到的每個車，刪除它，替換它在位置（i，j'）處的一個車和位置（i'，j）處的另一個車。

你最終得到的矩陣將只有沿第i行和第j列的矩陣。設A_1爲A的子矩陣，由其第一行和第一列組成。然後，A_1擁有隻包含 最後一行/ las列的屬性，因此您無需空間開銷即可解決A_1問題。對A的另外三個子矩陣（第n-1 + 1個最後一行和j個第一個柱子，等等）執行相同操作。

如果這不明確，請告訴我，我會給更多的細節。

Answer 2

嘗試這種解決方案

int main(){ 
    int n; 
    int chess[64][64]; 
    int hor[64],ver[64]; 
    //read chessboard 
    for(int i=0; i<n; i++) 
     for(int j=0; j<n; j++) 
      if(chess[i][j] == 1){ 
       hor[i] = 1; 
       ver[j] = 1; 
      } 
    int cntHor=0; 
    int cntVer=0; 
    for(int i=0; i<n; i++){ 
     if(hor[i] == 1) cntHor++; 
     if(ver[i] == 1) cntVer++; 
    } 
    int result = (cntHor+cntVer)*n-cntHor*cntVer; 
    cout<<result; 
    return 0 
}