常见算法题——螺旋矩阵

wuchangjian2021-11-15 20:10:18编程学习

正常版:给定一个数n打表n*n的螺旋矩阵

#include <iostream>

int main() {
    int n, x, y;
    std::cin >> n >> x >> y;
    int a[n][n];
    int tmp = 1;
    for (int i = 0; i < n / 2 + 1; ++i) {
        for(int j = i; j < n - i; ++j)
        	a[i][j]=tmp++;
        for(int j = i + 1; j < n - i; ++j)
        	a[j][n-i-1]=tmp++;
        for(int j = n - i - 2; j > i; --j)
        	a[n-i-1][j]=tmp++;
        for(int j = n - i - 1; j > i; --j)
        	a[j][i]=tmp++;
    }
    std::cout << a[x-1][y-1] << std::endl;
}

特殊版:给定 n x y求n*n大小的螺旋矩阵中下表为(x,y)的元素是多少

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long n,i,j,mi,ans=0;
    cin>>n>>i>>j;
    mi=min(i,min(j,min(n-i+1,n-j+1)));
    if(i<=j)
        ans=mi*(4*(n-1)-4*mi)+10*mi-4*n-3+i+j;
    else 
       ans=mi*(4*n-4*mi)+2*mi+1-i-j;
    cout<<ans;
    return 0;
}

特殊版递推形态(推荐)

long long DFS(int n,int i,int j)
{
    if(i==1)
        return j;
    if(j==n)
        return n+i-1;
    if(i==n)
        return 3*n-2-j+1;
    if(j==1)
        return 4*n-4-i+2;
    return (n-2,i-1,j-1)+4*(n-1);
    
}

并非原创,是洛谷大佬想的

发表评论    

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。