0ms c++ solution, very easy to understand


  • 0
    L
    //5 types of direction to which your next step will go, including END
    typedef enum DIRECTION{
    	LEFT = 0,
    	RIGHT,
    	UP,
    	DOWN,
    	END,
    }DIRECTION;
    
    /*core of this algorithm
    * @param: x --> index of rows of the matrix;
    * @param: y --> index of cols of the matrix;
    * @param: xLow --> index of very top of matrix;
    * @param: xHigh --> index of very bottom of matrix;
    * @param: yLow --> index of very left of matrix;
    * @param: yHigh --> index of very right of matrix;
    * @param: last --> direction of your last move, it's very important,
    	make it more clear of how to move to the next slot;
    
    * @description: I take the first case which is (last == RIGHT) for example,
    	if y hasn't reached the very right of the matrix, then the next move is to
    	let y plus by 1; if y has reached the very right of the matrix, natually,
    	the next move is to let x plus by 1, and go DOWN;
    
    	but what if x also reaches the its higher bound? This means the current
    	coordinates (x,y) is the last element in the matrix. At this time, we should
    	end the loop. The function NextPos will return an END value;
    
    	if (x+1, y) is still valid, the lower bound of x should plus by 1 in case that
    	when you are on going up, you visit the visited elements with an Y-axis value
    	of x(yes, x represents the Y-axis coordinate). Then return DOWN.
    
    	the other cases can be figure out in the same way.
    */
    DIRECTION NextPos(int &x, int &y, int &xLow, int &xHigh
    				, int &yLow, int &yHigh, DIRECTION last)
    {
    	if(last == RIGHT)
    	{
    		if(y < yHigh)
    		{
    			y++;
    			return RIGHT;
    		}
    		else
    		{
    			x++;
    			if(x > xHigh)
    				goto FINISH;
    			xLow++;
    			return DOWN;
    		}
    	}
    	else if(last == DOWN)
    	{
    		if(x < xHigh)
    		{
    			x++;
    			return DOWN;
    		}
    		else
    		{
    			y--;
    			if(y < yLow)
    				goto FINISH;
    			yHigh--;
    			return LEFT;
    		}
    	}
    	else if(last == LEFT)
    	{
    		if(y > yLow)
    		{
    			y--;
    			return LEFT;
    		}
    		else
    		{
    			x--;
    			if(x < xLow)
    				goto FINISH;
    			xHigh--;
    			return UP;
    		}
    	}
    	else if(last == UP)
    	{
    		if(x > xLow)
    		{
    			x--;
    			return UP;
    		}
    		else
    		{
    			y++;
    			if(y > yHigh)
    				goto FINISH;
    			yLow++;
    			return RIGHT;
    		}
    	}
    FINISH:
    	return END;
    }
    
    vector<int> spiralOrder(vector<vector<int> >& matrix)
    {
    	vector<int> ret;
    	if(matrix.size() <= 0)
    		return ret;
    
    	//initialize the variables, first go right;
    	DIRECTION lastdir = RIGHT;
    	int x = 0;
    	int y = -1;
    	int xLow = 0;
    	int xHigh = matrix.size() - 1;
    	int yLow = 0;
    	int yHigh = matrix[0].size() - 1;
    
    	while((lastdir = NextPos(x, y, xLow, xHigh, yLow, yHigh, lastdir)) != END)
    		ret.push_back(matrix[x][y]);
    
    	return ret;
    }
    

    in the comments, I think I make it clear of how the function NextPos() works.


Log in to reply
 

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