问题描述
小C发现了一种奇特的图案，叫做螺旋阵列。它由一串0和1组成，看起来像一个由外向内旋转的图形。小C想知道，能否根据给定的宽度来生成这样一个螺旋图案。
例如，宽度为5时的螺旋阵列如下：
11111
00001
11101
10001
11111
宽度为10时的螺旋阵列如下：
1111111111
0000000001
1111111101
1000000101
1011110101
1010010101
1010000101
1011111101
1000000001
1111111111
小C想知道，对于任意给定的宽度 n，是否能生成对应的螺旋图案，并且以一个二维数组的形式输出。
测试样例
样例1：
输入：
width = 5
输出：[[1, 1, 1, 1, 1], [0, 0, 0, 0, 1], [1, 1, 1, 0, 1], [1, 0, 0, 0, 1], [1, 1, 1, 1, 1]]
样例2：
输入：
width = 8
输出：[[1, 1, 1, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0, 0, 1], [1, 1, 1, 1, 1, 1, 0, 1], [1, 0, 0, 0, 0, 1, 0, 1], [1, 0, 1, 0, 0, 1, 0, 1], [1, 0, 1, 1, 1, 1, 0, 1], [1, 0, 0, 0, 0, 0, 0, 1], [1, 1, 1, 1, 1, 1, 1, 1]]
样例3：
输入：
width = 2
输出：[[1, 1], [0, 1]]
#include <cassert>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
std::vector<std::vector<int>> solution(int width) {
// Ensure the input width is greater than 1
assert(width > 1);
// Handle special cases
if (width == 2) {
return {{1, 1}, {0, 1}};
}
if (width == 3) {
return {{1, 1, 1}, {0, 0, 1}, {1, 1, 1}};
}
// Recursively generate a smaller spiral
vector<vector<int>> base = solution(width - 2);
// Initialize the first two rows
vector<vector<int>> res;
res.push_back(vector<int>(width, 1));
res.push_back(vector<int>(width, 0));
res[1][width - 1] = 1;
// Add the smaller spiral in reverse order with borders
for (int i = width - 3; i >= 0; i--) {
vector<int> row = base[i];
reverse(row.begin(), row.end());
row.push_back(0);
row.push_back(1);
res.push_back(row);
}
// Fix the second last element of the last row
res[res.size() - 1][res[0].size() - 2] = 1;
return res;
}
int main() {
// You can add more test cases here
std::vector<std::vector<int>> expected1 = {{1, 1, 1, 1, 1},
{0, 0, 0, 0, 1},
{1, 1, 1, 0, 1},
{1, 0, 0, 0, 1},
{1, 1, 1, 1, 1}};
std::vector<std::vector<int>> expected2 = {
{1, 1, 1, 1, 1, 1, 1, 1}, {0, 0, 0, 0, 0, 0, 0, 1},
{1, 1, 1, 1, 1, 1, 0, 1}, {1, 0, 0, 0, 0, 1, 0, 1},
{1, 0, 1, 0, 0, 1, 0, 1}, {1, 0, 1, 1, 1, 1, 0, 1},
{1, 0, 0, 0, 0, 0, 0, 1}, {1, 1, 1, 1, 1, 1, 1, 1}};
std::vector<std::vector<int>> expected3 = {{1, 1}, {0, 1}};
std::cout << (solution(5) == expected1) << std::endl;
std::cout << (solution(8) == expected2) << std::endl;
std::cout << (solution(2) == expected3) << std::endl;
return 0;
}