There is a robot starting at position (0, 0), the origin, on a 2D plane. Given a sequence of its moves, judge if this robot ends up at (0, 0) after it completes its moves.
The move sequence is represented by a string, and the character moves[i] represents its ith move. Valid moves are R (right), L (left), U (up), and D (down). If the robot returns to the origin after it finishes all of its moves, return true. Otherwise, return false.
Note: The way that the robot is "facing" is irrelevant. "R" will always make the robot move to the right once, "L" will always make it move left, etc. Also, assume that the magnitude of the robot's movement is the same for each move.
Example 1:
Input: "UD"
Output: true
Explanation: The robot moves up once, and then down once. All moves have the same magnitude, so it ended up at the origin where it started. Therefore, we return true.
Example 2:
Input: "LL"
Output: false
Explanation: The robot moves left twice. It ends up two "moves" to the left of the origin. We return false because it is not at the origin at the end of its moves.
We can simulate the position of the robot after each command.
Algorithm
Initially, the robot is at (x, y) = (0, 0). If the move is 'U', the robot goes to (x, y-1); if the move is 'R', the robot goes to (x, y) = (x+1, y), and so on.
publicbooleanjudgeCircle(String moves){int x =0, y =0;for(char move: moves.toCharArray()){if(move =='U') y--;elseif(move =='D') y++;elseif(move =='L') x--;elseif(move =='R') x++;}return x ==0&& y ==0;}
We are given an elevation map, heights[i] representing the height of the terrain at that index. The width at each index is 1. After V units of water fall at index K, how much water is at each index?
Water first drops at index K and rests on top of the highest terrain or water at that index. Then, it flows according to the following rules:
If the droplet would eventually fall by moving left, then move left.
Otherwise, if the droplet would eventually fall by moving right, then move right.
Otherwise, rise at it's current position.
Here, "eventually fall" means that the droplet will eventually be at a lower level if it moves in that direction. Also, "level" means the height of the terrain plus any water in that column.
We can assume there's infinitely high terrain on the two sides out of bounds of the array. Also, there could not be partial water being spread out evenly on more than 1 grid block - each unit of water has to be in exactly one block.
Example 1:
Input: heights = [2,1,1,2,1,2,2], V = 4, K = 3
Output: [2,2,2,3,2,2,2]
Explanation:
# #
# #
## # ###
#########
0123456 <- index
The first drop of water lands at index K = 3:
# #
# w #
## # ###
#########
0123456
When moving left or right, the water can only move to the same level or a lower level.
(By level, we mean the total height of the terrain plus any water in that column.)
Since moving left will eventually make it fall, it moves left.
(A droplet "made to fall" means go to a lower height than it was at previously.)
# #
# #
## w# ###
#########
0123456
Since moving left will not make it fall, it stays in place. The next droplet falls:
# #
# w #
## w# ###
#########
0123456
Since the new droplet moving left will eventually make it fall, it moves left.
Notice that the droplet still preferred to move left,
even though it could move right (and moving right makes it fall quicker.)
# #
# w #
## w# ###
#########
0123456
# #
# #
##ww# ###
#########
0123456
After those steps, the third droplet falls.
Since moving left would not eventually make it fall, it tries to move right.
Since moving right would eventually make it fall, it moves right.
# #
# w #
##ww# ###
#########
0123456
# #
# #
##ww#w###
#########
0123456
Finally, the fourth droplet falls.
Since moving left would not eventually make it fall, it tries to move right.
Since moving right would not eventually make it fall, it stays in place:
# #
# w #
##ww#w###
#########
0123456
The final answer is [2,2,2,3,2,2,2]:
#
#######
#######
0123456
Example 2:
Input: heights = [1,2,3,4], V = 2, K = 2
Output: [2,3,3,4]
Explanation:
The last droplet settles at index 1, since moving further left would not cause it to eventually fall to a lower height.
Example 3:
Input: heights = [3,1,3], V = 5, K = 1
Output: [4,4,4]
Note:
heights will have length in [1, 100] and contain integers in [0, 99].
vector<int> pourWater(vector<int>& heights, int V, int K) {
for (int i = 0; i < V; ++i) {
int l = K, r = K, n = heights.size();
while (l > 0 && heights[l] >= heights[l - 1]) --l;
while (l < K && heights[l] == heights[l + 1]) ++l;
while (r < n - 1 && heights[r] >= heights[r + 1]) ++r;
while (r > K && heights[r] == heights[r - 1]) --r;
(heights[l] < heights[K]) ? ++heights[l] : ++heights[r];
}
return heights;
}
vector<int>pourWater(vector<int>& heights,int V,int K){while(V--)drop(heights, K);return heights;}private:voiddrop(vector<int>& heights,int K){int best = K;for(int d =-1; d <=1; d +=2){int i = K + d;while(i >=0&& i < heights.size()&& heights[i]<= heights[i - d]){if(heights[i]< heights[best]) best = i;
i += d;}if(best != K)break;}++heights[best];}
Input is a array represent how the height of water is at each position, the number of water will be poured, and the pour position. Print the land after all water are poured.
Example: input land height int[]{5,4,2,1,3,2,2,1,0,1,4,3} The land is looks ike:
