好久没写文章了...
自罚30大板
在刷leetcode
就继续更新吧
Q：Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
eg 1:
Input:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]
eg 2:
Input:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]
题目很好理解，就是把一个矩阵螺旋着输出。
看到这个题目，我首先就想着使用深度优先进行搜索。这有点像迷宫的搜索，我们可以定义搜索规则如下：
定义一个辅助矩阵，判断这个cell是否被搜索过。
eg
[
[1, 1, 1],
[1, 1, 1],
[1, 1, 1]
]
在这里，1代表未被搜索过，0代表已经被搜索过。
当我们搜索完第一行，matrix变成
[
[0, 0, 0 ],
[1, 1, 1 ],
[1, 1, 1]
]
这时候我们只有一个方向可以继续往下走，就是朝下，因为上下左右都是无法走的（0也是无法走的），类似地，可以一直走到这个状态
[
[0, 0, 0 ],
[0, 1, 0 ],
[0, 0, 0 ]
]
然后就只剩1可以走啦，也就是我们的搜索结束了ORZ
也就是说我们需要定义的变量有以下几个：
1 现在前进的方向direction当只有一个方向可以前行的时候进行改变
2 保存答案的数组
3 现在的位置，以便于下一次进行Move的时候方便找到初始位置
4 状态数组
然后就开始愉快地撸码。
/**
direction： 方向
cur_i，cur_j：现在的位置
recMatrix： 状态数组
ans： 保存答案的数组
**/
class Solution {
void move(int direction,int cur_i, int cur_j, vector<vector<int>>& matrix, vector<vector<int>>& recMatrix, vector<int>& ans){
if(direction == 0){
if( cur_j >= matrix[0].size() || recMatrix[cur_i][cur_j] == 0 ) return; //先判断是否还有路可走，没有的话返回
for( int j = cur_j; ;j++){ //然后开始走，并且记录答案
if( j < matrix[cur_i].size() && recMatrix[cur_i][j] != 0 ){
cout << matrix[cur_i][j] << endl;
ans.push_back(matrix[cur_i][j]);
recMatrix[cur_i][j] = 0;
cur_j =j;
}
else break;
}
direction = 1;
move(direction, cur_i + 1, cur_j , matrix, recMatrix, ans);
}
else if(direction == 1){
if( cur_i >= matrix.size() || recMatrix[cur_i][cur_j] == 0 ) return;
for( int i = cur_i; ;i++){
if( i < matrix.size() && recMatrix[i][cur_j] != 0 ){
ans.push_back(matrix[i][cur_j]);
recMatrix[i][cur_j] = 0;
cur_i =i;
}
else break;
}
direction = 2;
move(direction, cur_i , cur_j - 1, matrix, recMatrix, ans);
}
else if(direction == 2){
if( cur_j < 0 || recMatrix[cur_i][cur_j] == 0 ) return;
for( int j= cur_j;; j--){
if( j >= 0 && recMatrix[cur_i][j] != 0 ){
ans.push_back(matrix[cur_i][j]);
recMatrix[cur_i][j] = 0;
cur_j =j;
}
else break;
}
direction = 3;
move(direction, cur_i - 1, cur_j , matrix, recMatrix, ans);
}
else if(direction == 3){
if( cur_i < 0 || recMatrix[cur_i][cur_j] == 0 ) return;
for( int i = cur_i; ;i--){
if( i >= 0 && recMatrix[i][cur_j] != 0 ){
ans.push_back(matrix[i][cur_j]);
recMatrix[i][cur_j] = 0;
cur_i =i;
}
else break;
}
direction = 0;
move(direction, cur_i , cur_j + 1, matrix, recMatrix, ans);
}
}
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> res;
// 定义的状态举证
vector<vector<int>> recMatrix;
if(matrix.size() ==0 ) return res;
// 初始化
for( int i = 0; i< matrix.size(); i++){
vector<int> tempMatrix;
for( int j = 0; j<matrix[i].size(); j++ ){
tempMatrix.push_back(1);
}
recMatrix.push_back(tempMatrix);
}
// direction 0:right 1:down 2:left 3:up
int direction = 0;
move(0, 0, 0, matrix, recMatrix, res);
return res;
}
};
提交结果 AC beats 100% 看来只有这一个解了。其实这个状态数组完全是不需要的，但是我太懒了，AC了就不想改了，读者也可是实现抛弃这个状态数组进行实现。
