codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
/// Problem statement: Fill a W X H matrix in spiral fashion outside to inside clockwise /// For ex: 4 X 6 matrix would look like /// 1 2 3 4 /// 16 17 18 5 /// 15 24 19 6 /// 14 23 20 7 /// 13 22 21 8 /// 12 11 10 9 /// /// My solution: I created a function toCirBox(i, j, w, h) /// which can directly calculate the value of any element at index /// (i, j) in a matrix of dimension of (w x h) /// Space allocated is none, number of operations are min(w, h) + K /// to calculate one element #include <iostream> #include <cstdlib> using namespace std; int toCirBox(int i, int j, int w, int h) { int ii = i; if(i >= w/2 ) ii = w-1 - i; int jj = j; if(j >= h/2 ) jj = h-1 - j; int offset = 1; for(int ww = w, hh = h, iii = ii, jjj = jj; iii && jjj; --iii, --jjj, ww -= 2, hh -= 2) { offset += 2 * (ww + hh) - 4; } if(ii >= jj) { // Row case if(j == jj) offset += i - jj; // Left to right else offset += 2 * (w - 2 * jj) - 2 + (h - 2 * jj - 2) - (i - jj - 1); // Right to left } else { // Col case if(i < w/2) offset += 2 * (w - 2 * ii) + 2 * (h - 2 * ii - 2) - (j - ii); // Bottom to top else offset += (w - 2 * ii) + (j - ii - 1); // Top to bottom } // assert(0 <= offset && offset <= w * h); // assert( isNotRepeated(offset) ); return offset; } int main(int argc, char *const *argv) { int w = 3, h = 3; if(argc != 3) { cout << "Bad arguments" << endl; } else { w = atoi(argv[1]); h = atoi(argv[2]); } for(int j = 0; j < h; ++j) { for(int i = 0; i < w; ++i) { cout << toCirBox(i, j, w, h) << '\t'; } cout << endl; } } // EOF
Private
[
?
]
Run code
Submit