方陣的主對角線之上稱為“上三角”屿讽。
請你設(shè)計一個用于填充n階方陣的上三角區(qū)域的程序。填充的規(guī)則是：使用1贿讹，2渐逃，3….的自然數(shù)列，從左上角開始民褂，按照順時針方向螺旋填充茄菊。
例如：當(dāng)n=3時，輸出：
1 2 3
6 4
5
當(dāng)n=4時赊堪，輸出：
1 2 3 4
9 10 5
8 6
7
當(dāng)n=5時面殖，輸出：
1 2 3 4 5
12 13 14 6
11 15 7
10 8
9
程序運行時，要求用戶輸入整數(shù)n（3~20）
程序輸出：方陣的上三角部分哭廉。
要求格式：每個數(shù)據(jù)寬度為4脊僚，右對齊。
//
// s_20.cpp
// swordOffer
//
// Created by YangKi on 2017/2/14.
// Copyright ? 2017年 yangqi916. All rights reserved.
//
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
class Solution {
private:
vector<int>res;
int currentDirection = 0;
int rowIncre[3] = {0, 1, -1};
int colIncre[3] = {1, -1, 0};
int rows = 0;
int cols = 0;
bool isValid(int row, int col, int n) {
if((row >= 0 && row < n) && (col >= 0 && col < n-row) )
return true;
return false;
}
public:
vector<int> printMatrix(vector<vector<int> > matrix, int n) {
rows = (int)matrix.size();
if (rows == 0)
return res;
cols = (int)(matrix[0].size());
if(cols == 0)
return res;
vector<vector<bool>>isVisited(rows ,vector<bool>(cols, false));
int curRow = 0;
int curCol = 0;
int cnt = 0;
int maxnodes = (n*(n+1)) / 2;
while (cnt < maxnodes) {
cnt++;
isVisited[curRow][curCol] = true;
res.push_back(matrix[curRow][curCol]);
if (!isValid(curRow + rowIncre[currentDirection], curCol + colIncre[currentDirection], n)
|| isVisited[curRow + rowIncre[currentDirection]][curCol + colIncre[currentDirection]] == true) {
// 沿著原來的方向取下一個位置是非法的,需要換方向
currentDirection = (currentDirection + 1) % 3;
}
//取下一個位置
curRow += rowIncre[currentDirection];
curCol += colIncre[currentDirection];
}
return res;
}
};
