54. Spiral Matrix
Problem's Link
----------------------------------------------------------------------------
Mean:
顺时针漩涡状打印二维数组的值.
analyse:
控制四个边界即可.
Time complexity: O(N)
view code
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public :
vector < int > spiralOrder( vector < vector < int >> & matrix)
{
int row = matrix . size();
if( ! row) return vector < int >( 0);
int col = matrix [ 0 ]. size();
if( ! col) return vector < int >( 0);
vector < int > res( row * col);
int u = 0 , d = row - 1 , l = 0 , r = col - 1 , cnt = 0;
while( 1)
{
for( int i = l; i <= r; ++ i)
res [ cnt ++ ] = matrix [ u ][ i ];
++ u;
if( u > d) break;
for( int i = u; i <= d; ++ i)
res [ cnt ++ ] = matrix [ i ][ r ];
-- r;
if( l > r) break;
for( int i = r; i >= l; -- i)
res [ cnt ++ ] = matrix [ d ][ i ];
-- d;
if( u > d) break;
for( int i = d; i >= u; -- i)
res [ cnt ++ ] = matrix [ i ][ l ];
++ l;
if( l > r) break;
}
return res;
}
};
int main()
{
int n , m;
while( cin >>n >> m)
{
vector < vector < int >> mat(n , vector < int >( m , 0));
for( int i = 0; i <n; ++ i)
{
for( int j = 0; j < m; ++ j)
cin >> mat [ i ][ j ];
}
Solution solution;
vector < int > res = solution . spiralOrder( mat);
for( auto p: res)
cout <<p << " ";
cout << endl;
}
return 0;
}
/*
*/
using namespace std;
class Solution
{
public :
vector < int > spiralOrder( vector < vector < int >> & matrix)
{
int row = matrix . size();
if( ! row) return vector < int >( 0);
int col = matrix [ 0 ]. size();
if( ! col) return vector < int >( 0);
vector < int > res( row * col);
int u = 0 , d = row - 1 , l = 0 , r = col - 1 , cnt = 0;
while( 1)
{
for( int i = l; i <= r; ++ i)
res [ cnt ++ ] = matrix [ u ][ i ];
++ u;
if( u > d) break;
for( int i = u; i <= d; ++ i)
res [ cnt ++ ] = matrix [ i ][ r ];
-- r;
if( l > r) break;
for( int i = r; i >= l; -- i)
res [ cnt ++ ] = matrix [ d ][ i ];
-- d;
if( u > d) break;
for( int i = d; i >= u; -- i)
res [ cnt ++ ] = matrix [ i ][ l ];
++ l;
if( l > r) break;
}
return res;
}
};
int main()
{
int n , m;
while( cin >>n >> m)
{
vector < vector < int >> mat(n , vector < int >( m , 0));
for( int i = 0; i <n; ++ i)
{
for( int j = 0; j < m; ++ j)
cin >> mat [ i ][ j ];
}
Solution solution;
vector < int > res = solution . spiralOrder( mat);
for( auto p: res)
cout <<p << " ";
cout << endl;
}
return 0;
}
/*
*/