C++配列——マトリックス関連テーマ

行列相関問題(平方行列I~III、蛇形行列)
文書ディレクトリ

行列関連練習問題(平方行列I~III、蛇形行列)

一、平方行列I

二、二乗行列II

三、平方行列III

四、蛇行行列又は称回型行列

一、平方行列I
平方行列I題目詳細この題目はAcWingのウェブサイトの上の題目で、以下は題解です
サンプルを入力:
1
2
3
4
5
0
出力サンプル:
1
1 1 1 1
1 1 1 1 2 1 1 1 1
1 1 1 1 1 2 2 1 1 2 2 1 1 1 1 1
1 1 1 1 1 1 2 2 2 1 1 2 3 2 1 1 2 2 2 1 1 1 1 1 1
構想:マンハッタン距離、この行列の中で1桁ごとに記入する数はこの位置から4つの境界までの最短距離です
すなわちf[i][j]=min(min(i,j),min(n-i,n-j)+1);i,jは1から
コードは次のように実装されます.

#include 
#include 
#include 

using namespace std;

int main(void)
{
    int n;
    while (cin >> n, n)
    {
        for (int i = 1; i <= n; ++ i)
        {
           for (int j = 1; j <= n; ++ j)
           {
               int k = min(min(i, j), min(n-i, n-j)+1);
               cout << k << ' ';
           }
           cout << endl;
        }
        cout << endl;
    }
    
    return 0;
}

二、平方行列II
平方マトリックスII詳細本題はAcWingサイト上の題で、以下は題解
サンプルを入力:
入力サンプル:1 2 3 4 5 0
出力サンプル:1
1 2 2 1
1 2 3 2 1 2 3 2 1
1 2 3 4 2 1 2 3 3 2 1 2 4 3 2 1
1 2 3 4 5 2 1 2 3 4 3 2 1 2 3 4 3 2 1 2 5 4 3 2 1
構想:よく観察すると、f[i][j]=?
明らかに法則は以下の通りである:i=j,f[i][j]=1 i!=j , f [ i ] [ j ] = a b s ( i − j ) + 1 i = j, f[i][j] = 1\\i != j, f[i][j] = abs(i-j) +1 i=j,f[i][j]=1i!=j,f[i][j]=abs(i−j)+1コードは以下のように実現される.

#include 
#include 
#include 

using namespace std;

int main(void)
{
    int n;
    while (cin >> n, n)
    {
        for (int i = 1; i <= n; ++ i)
        {
            
            for (int j = 1; j <= n; ++ j)
            {
                if (i == j)  cout << '1' << ' ';
                else  cout << abs(j - i) + 1 << ' ';
            }
            cout << endl;
        }
        cout << endl;
    }
    
    return 0;
}

三、平方行列III
平方行列III詳細本題はAcWingサイト上の題で、以下は題解
入力サンプル:1 2 3 4 5 0
出力サンプル:1
1 2 2 4
1 2 4 2 4 8 4 8 16
1 2 4 8 2 4 8 16 4 8 16 32 8 16 32 64
1 2 4 8 16 2 4 8 16 32 4 8 16 32 64 8 16 32 64 128 16 32 64 128 256
考え方:最後の行列を例にとると、すべての数を2のn次方に変換し、nの行列は以下の通りである.
0 1 2 3 4
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
コードは次のように実装されます.

#include 
#include 
#include 

using namespace std;

int main(void)
{
    int n;
    while (cin >> n, n)
    {
        for (int i = 0; i < n; ++ i)
        {
            for (int j = 0, k = i; j < n; ++ j, ++ k)
               cout << (long long)pow(2, k) << ' ';
            cout << endl;
        }
        cout << endl;
    }
    
    return 0;
}

四、蛇形行列又は称回型行列
蛇形マトリクス詳細本題はAcWingサイト上の題で、以下は題解
入力サンプル:3 3
出力サンプル:1 2 3 8 9 4 7 5
考え方:1->2->3を順番に記入して下に曲がる・・・字型に戻す
主に2つの判断があり、1つは境界に対する判断であり、もう1つはその位置が占有されているか否かの判断(カーブによるもの)であり、境界に対する判断には4つのif判断が必要であり、上、下、左、右の4つの境界に対応し、占有位置に対する判断も同様であり、ある位置が占有されているか否かを判断したため、4つの状況が発生する可能性があり、対応するのは左、上、右、右、カーブを下りる
問題を単純化するために、ここではオフセット量の方法を使用します.コアコードは次のとおりです.

int a = x + dx[d], b = y + dy[d];

//           ，   

 if (a < 0 || a >= n || b < 0 || b >= m || q[a][b])
 {
      d = (d + 1) % 4;//      
      a = x + dx[d];
      b = y + dy[d];          
 }

完全なコード実装:

#include 
#include 
#include 

using namespace std;

const int N = 110;
int q[N][N], m, n;

int main(void)
{
    int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
    cin >> n >> m;
    int x = 0, y = 0, d = 1;
    for (int i = 1; i <= n * m; ++ i)
    {
        q[x][y] = i;
        int a = x + dx[d], b = y + dy[d];
        if (a < 0 || a >= n || b < 0 || b >= m || q[a][b])
        {
            d = (d + 1) % 4;
            a = x + dx[d];
            b = y + dy[d];
        }
        x = a, y = b;
    }
    for (int i = 0; i < n; ++ i)
    {
        for (int j = 0; j < m; ++ j)
           cout << q[i][j] << ' ';
        cout << endl;
    }
    
    return 0;
}

以上は今回分かち合ったすべての内容で、観覧に感謝して、もし間違いがあれば指摘して、ありがとうございます!