A rectangular mosaic floor has m rows and n columns of tiles; each tile is either amber (marked '0') or jade (marked '1'). Starting on the tile in the top-left corner, a floor inspector may step at each move to the tile directly to the right or the tile directly below, and must finish on the tile in the bottom-right corner. Every tile the inspector stands on -- including the very first and the very last -- counts toward a running tally of amber and jade tiles visited. Decide whether some such route lets the inspector finish having visited exactly as many amber tiles as jade tiles.
The first line contains two integers m and n. Each of the next m lines contains a string of exactly n characters, each either '0' (amber) or '1' (jade), describing one row of the floor from left to right.
Print YES if some valid route visits an equal number of amber and jade tiles, or NO otherwise.
Example 1
Input
2 3 000 111
Expected
YES
Explanation
The route (0,0) -> (0,1) -> (1,1) -> (1,2) visits tiles '0','0','1','1' -- two amber tiles and two jade tiles, so the counts are equal. Output YES.
Example 2
Input
3 2 00 00 01
Expected
NO
Explanation
The whole floor has exactly one jade tile, sitting at the bottom-right corner. Every valid route has length m+n-1=4 and must end on that corner, so every route visits exactly one jade tile and three amber tiles -- the counts can never be equal. Output NO.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →