C++：行列内のA[i][j]=0となるインデックス（i, j）の最大差を求める方法

本記事では、n×nのサイズを持つ行列が与えられたとき、a[i][j] = 0となる要素のインデックス（i, j）の差の最大値を求める方法を解説します。この問題では、行列内に少なくとも1つの0が存在することが前提となります。

例で理解しよう

入力例1

int matrix[][] = {
   {0, 1, 1},
   {0, 0, 0},
   {4, 5, 1}}

出力

A[i][j] = 0となるインデックス（i, j）の最大差：1

説明

この行列では、matrix[0][0]、matrix[1][0]、matrix[1][1]、matrix[1][2]の位置に0が存在します。各位置における|i − j|の値を計算すると、matrix[1][0]のとき|1 − 0| = 1が最大となり、したがって最大差は1です。

入力例2

int matrix[][] = {
   {0, 1, 1},
   {0, 2, 9},
   {4, 0, 1}}

出力

A[i][j] = 0となるインデックス（i, j）の最大差：1

説明

この行列では、matrix[0][0]、matrix[1][0]、matrix[2][1]の位置に0が存在します。それぞれの|i − j|を比較しても最大値は1であるため、最大差は1となります。

プログラムで使用するアプローチ

• 少なくとも1つの0を含む行列を入力として受け取ります。
• 行と列の最大サイズ（n×n）を定義します。
• 最大差の値を格納するための一時変数を用意します。
• iを0から行サイズまでループさせます。
• その内側で、jを0から列サイズまでループさせます。
• matrix[i][j] == 0であるかどうかを判定します。
• 条件を満たす場合、インデックスの差（abs(i − j)）と現在の最大値を比較し、大きい方を新しい最大値として更新します。
• すべてのループが終了したら、最大値を返します。
• 結果を出力します。

実装例

#include <bits/stdc++.h>
using namespace std;
#define row 3
#define col 3
// 最大差を求める関数
int maximum(int matrix[row][col]){
   int max_val = 0;
   for (int i = 0; i < row; i++){
      for (int j = 0; j < col; j++){
         if (matrix[i][j] == 0){
            max_val = max(max_val, abs(i - j));
         }
      }
   }
   return max_val;
}
int main(){
   int matrix[row][col] = {
      { 1, 2, 0},
      { 0, 4, 0},
      { 0, 1, 0}};
   cout<<"Maximum difference of indices with A[i][j] = 0 is: "<<maximum(matrix);
   return 0;
}

出力結果

上記のコードを実行すると、以下の出力が得られます。

Maximum difference of indices with A[i][j] = 0 is: 2

このコードでは、0が存在する位置はmatrix[0][2]、matrix[1][0]、matrix[1][2]、matrix[2][0]、matrix[2][2]であり、それぞれの|i − j|は2、1、1、2、0となります。したがって、最大差は2という結果になります。