Background
In a 2d game that I play, each screen is a 2d grid of tiles with walls and walkable tiles, with the player only able to travel on walkable tiles, and being stopped by walls. When the player walks past the edge of the screen, he will travel to the adjacent screen on the map, with the player's relative screen location on the opposite side of the edge he entered in the previous screen (Think about it this way: when he walks left to another screen, it makes sense that he will be on the right of next screen).
There is a glitch that you can perform that will allow the player to glitch into a wall and, in certain cases, clip out of the map. After that, the player can travel through walls. Since the player is out of the map, if he travels past any edge of the screen, he will be warped to the other side relative to the screen, but the actual 2d grid will be the same (the game tries to determine where the player is to generate the new screen, but because he is out of bounds, it won't find a valid screen to generate, so the screen won't change). If the player travels out of a wall and into a walkable tile, he can't walk through walls until he is in a wall again. This rule also applies when the player warps to the other side of the screen after he travels through an edge; if he warps from a wall to a walkable tile, he will not be able to go through walls. On the flip side, if the player warps from a walkable tile to a wall, he will clip into the wall and be able to go through walls again.
A side effect of this glitch is that the player's actual coordinates in the game map will change based on which edge he travels through. When the player travels through the top or bottom edge, his y-coordinate will increase or decrease by 1 respectively. Similarly, when the player travels through the left or right edge, his x-coordinate will decrease or increase by 1 respectively.
Challenge
Given a configuration of walls and walkable tiles of the screen, is it possible for the player to reach a certain map coordinate? Assume that the player is always out of bounds (so the screen configuration always stays the same), and that the player starts at map coordinates (0,0)
. You can place the initial position of the player relative to the screen anywhere you want (you can place the player in a wall or a walkable tile). You can also optionally take in the dimensions, n
by m
, of the screen.
Example
Let's say the screen is 3 by 4 has the following configuration (1
represent walls, 0
represent walkable tiles):
1 0 0 1
1 0 0 1
1 0 0 1
Can the player get to the coordinates (-2,0)
? Let's start by placing the player on one of the walkable tiles. I will denote the player with a letter P
:
1 0 0 1
1 0 P 1
1 0 0 1
Because there are two columns of walls lining the left and right edge of the screen, the player cannot access those two edges. Therefore, he can only go through the top and bottom edge. In other words, the y-coordinate can change, but the x-coordinate stays the same. The same goes for any other walkable tile on the screen. So (-2,0)
can't be reached by placing the player on a walkable tile. But what if you place the player on one of the walls; for example, one of the left ones?
1 0 0 1
P 0 0 1
1 0 0 1
First, if the player travels to the right, he will pop out of the wall, resulting in the situation described above. In this case, the player can travel through the left edge to get to (-1,0)
, but he will be warped to the right side of the screen:
1 0 0 1
1 0 0 P
1 0 0 1
The player is now at (-1,0)
, but the goal is to get to (-2,0)
! The player has to go through the left edge again, but it can't be reached. If the player walks to the left onto the walkable tile, he will pop out of the wall and won't be able to warp back into the wall again. Going through the top or bottom edge won't help, because the player will still be in the walls on the right side, which is not connected to the left side. Travelling through the right edge will warp the player back to the left walls, but at the same time, it will increase his x-coordinate by 1, bringing the player back to (0,0)
.
Lastly, if you place the player on one of the right walls, like so:
1 0 0 P
1 0 0 1
1 0 0 1
You will find that reaching (-2,0)
is still impossible. Using a similar reasoning as above, you can determine that in order for the player to access the left edge to get closer to (-2,0)
, the player will first have to travel to the right. That will give him access to the left edge, but that will increase his x-coordinate by 1, so his coordinates are now (1,0)
. Now, travelling through the left edge as we intended initially will bring the player back to (0,0)
, instead of (-1,0)
like we wanted. Popping out of the wall at the start by going to the left is also not an option, because it will result in the first situation described above.
So, it is impossible to reach (-2,0)
with the above screen configuration.
Input
Your code should take in a rectangular 2d list (or any representation of a 2d grid) of two distinct characters or numbers, one representing walls and the other representing walkable tiles, for the screen configuration. It should also take in a coordinate pair with integer coordinates. Your code can optionally take in the dimensions n
and m
.
Scoring
This is code-golf, so the shortest code in byte count wins!
Test Cases
Uses 0
for walkable tiles and 1
for walls. The 2d ascii grid above each test case is just for reference.
n, m, coordinates, configuration
--> Output
False Cases
------------
1 0 0 1
1 0 0 1
1 0 0 1
3, 4, (-2, 0), [[1, 0, 0, 1], [1, 0, 0, 1], [1, 0, 0, 1]]
--> False
1 0 1
0 1 0
1 0 1
3, 3, (0, 2), [[1, 0, 1], [0, 1, 0], [1, 0, 1]]
--> False
1 0 1 1 1 1 1 1 1
1 1 0 0 0 1 0 1 1
1 1 1 0 1 0 1 0 1
0 1 0 1 1 1 1 1 0
1 0 1 1 1 1 1 1 1
5, 9, (2, 2), [[1, 0, 1, 1, 1, 1, 1, 1, 1], [1, 1, 0, 0, 0, 1, 0, 1, 1], [1, 1, 1, 0, 1, 0, 1, 0, 1], [0, 1, 0, 1, 1, 1, 1, 1, 0], [1, 0, 1, 1, 1, 1, 1, 1, 1]]
--> False
1 0 0 0 1 0 0 0 1 0 0 0 1
0 1 1 1 0 1 1 1 0 1 1 1 0
0 1 1 1 1 0 1 1 1 1 1 1 0
1 1 1 1 1 1 0 1 1 1 1 1 1
1 1 0 1 1 1 0 1 1 1 0 1 1
0 0 1 0 0 0 1 0 0 0 1 0 0
6, 13, (-200, 100), [[1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1], [0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0], [0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0], [1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1], [1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1], [0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0]]
--> False
True Cases
------------
0 0 0 1
1 0 0 1
1 0 0 1
3, 4, (-2, -2), [[0, 0, 0, 1], [1, 0, 0, 1], [1, 0, 0, 1]]
--> True
1 1 1 1
1 0 0 0
1 0 0 0
1 0 0 0
4, 4, (100, 100), [[1, 1, 1, 1], [1, 0, 0, 0], [1, 0, 0, 0], [1, 0, 0, 0]]
--> True
0 0 1 0 0
0 0 1 0 0
1 1 1 1 1
0 0 1 0 0
0 0 1 0 0
5, 5, (1, -1), [[0, 0, 1, 0, 0], [0, 0, 1, 0, 0], [1, 1, 1, 1, 1], [0, 0, 1, 0, 0], [0, 0, 1, 0, 0]]
--> True
0 0 1 0 0
1 1 1 0 0
0 0 1 1 1
0 0 1 0 0
4, 5, (-123, 456) [[0, 0, 1, 0, 0], [1, 1, 1, 0, 0], [0, 0, 1, 1, 1], [0, 0, 1, 0, 0]]
--> True
1 0 0 0 1 0 0 0 1 0 1 1 0
0 1 1 1 0 1 1 1 0 1 0 0 1
1 1 1 1 1 0 1 1 1 1 1 1 0
1 1 1 1 1 1 0 1 1 1 1 1 0
1 1 0 1 1 1 0 1 1 1 1 1 0
0 0 1 0 0 0 1 0 0 0 1 0 0
6, 13, (-200, 100), [[1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0], [0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1], [1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0], [1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0], [1, 1, 0, 1, 1, 1, 0, 1, 1, ,1 ,1 ,1 ,0], [0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0]]
--> True