Modern C++ Solution using functors


  • 0
    L
    vector<vector<int>> generateMatrix(int n)
    {
    	using dv = vector<vector<int>>;
    	if (!n) return dv();
    
    	dv spiral_m(n, vector<int>(n));
    	int incr = 1;
    
    	auto right = [&](int &row, int &col, dv &spiral_m, int n, int &incr) {
    		while (col < n && 
    			   spiral_m[row][col] == 0) {
    			spiral_m[row][col] = incr++;
    			col++;
    		}
    		// finished - so backtrack once and move down 1
    		col--; row++;
    	};
    
    	auto down = [&](int &row, int &col, dv &spiral_m, int n, int &incr) {
    		while (row < n &&
    			   spiral_m[row][col] == 0) {
    			spiral_m[row][col] = incr++;
    			row++;
    		}
    		// finished - so backtrack once and left 1
    		row--; col--;
    	};
    
    	auto left = [&](int &row, int &col, dv &spiral_m, int n, int &incr) {
    		while (col >= 0 && 
    			   spiral_m[row][col] == 0) {
    			spiral_m[row][col] = incr++;
    			col--;
    		}
    		// finished - so backtrack once and move up 1
    		col++; row--;
    	};
    
    	auto up = [&](int &row, int &col, dv &spiral_m, int n, int &incr) {
    		while (row >= 0 &&
    			   spiral_m[row][col] == 0) {
    			spiral_m[row][col] = incr++;
    			row--;
    		}
    		// finished - so backtrack once and move right 1
    		row++; col++;
    	};
    
    	vector<std::function<void(int &, int &, dv &, int, int &)>> functors = {right, down, left, up};
    
    	int row = 0, col = 0;
    	int function_wrapper = 0;
    	
    	// the number of time to loop in a spiral grows at n+n-1;
    	// consider the pattern for size n:
    	//
    	// n | loop
    	// 1 | 1
    	// 2 | 3
    	// 3 | 5
    	// 5 | 7
    	int num_times_to_loop = (2 * n) - 1;
    
    	while (num_times_to_loop) {
    		functors.at(function_wrapper % functors.size())(row, col, spiral_m, n, incr);
    		function_wrapper++;
    		num_times_to_loop--;
    	}
    	return spiral_m;
    }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.