Missing test case for 1036. Escape a Large Maze #19385
Description
LeetCode Username
Problem number, title, and link
- Escape a Large Maze https://leetcode.com/problems/escape-a-large-maze/
Category of the bug
- Problem description
- Solved examples
- Problem constraints
- Problem hints
- Incorrect or missing "Related Topics"
- Incorrect test Case (Output of test case is incorrect as per the problem statement)
- Missing test Case (Incorrect/Inefficient Code getting accepted because of missing test cases)
- Editorial
- Programming language support
Description of the bug
A wrong solution can pass the Leetcode OJ with existing test cases.
Language used for code
Python3
Code used for Submit/Run operation
def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:
blocked = set(map(tuple, blocked))
def bfs(source, target):
queue = collections.deque([tuple(source)])
visited = set([tuple(source)])
directions = [[-1, 0], [0, 1], [1, 0], [0, -1]]
distance = 0
while queue:
size = len(queue)
for _ in range(size):
x, y = queue.popleft()
if [x, y] == target:
return True
for xx, yy in directions:
new_x, new_y = x + xx, y + yy
if new_x < 0 or new_x >= 10**6 or new_y < 0 or new_y >= 10**6:
continue
if (new_x, new_y) in visited or (new_x, new_y) in blocked:
continue
queue.append((new_x, new_y))
visited.add((new_x, new_y))
distance += 1
if distance > len(blocked):
return True
return bfs(source, target) and bfs(target, source)
Expected behavior
For the following test case, the above code returns True even though the correct answer is False. So this solution is wrong. But the existing test cases don't include this test case, making a wrong solution pass the existing tests.
[[199,0],[198,1],[197,2],[196,3],[195,4],[194,5],[193,6],[192,7],[191,8],[190,9],[189,10],[188,11],[187,12],[186,13],[185,14],[184,15],[183,16],[182,17],[181,18],[180,19],[179,20],[178,21],[177,22],[176,23],[175,24],[174,25],[173,26],[172,27],[171,28],[170,29],[169,30],[168,31],[167,32],[166,33],[165,34],[164,35],[163,36],[162,37],[161,38],[160,39],[159,40],[158,41],[157,42],[156,43],[155,44],[154,45],[153,46],[152,47],[151,48],[150,49],[149,50],[148,51],[147,52],[146,53],[145,54],[144,55],[143,56],[142,57],[141,58],[140,59],[139,60],[138,61],[137,62],[136,63],[135,64],[134,65],[133,66],[132,67],[131,68],[130,69],[129,70],[128,71],[127,72],[126,73],[125,74],[124,75],[123,76],[122,77],[121,78],[120,79],[119,80],[118,81],[117,82],[116,83],[115,84],[114,85],[113,86],[112,87],[111,88],[110,89],[109,90],[108,91],[107,92],[106,93],[105,94],[104,95],[103,96],[102,97],[101,98],[100,99],[99,100],[98,101],[97,102],[96,103],[95,104],[94,105],[93,106],[92,107],[91,108],[90,109],[89,110],[88,111],[87,112],[86,113],[85,114],[84,115],[83,116],[82,117],[81,118],[80,119],[79,120],[78,121],[77,122],[76,123],[75,124],[74,125],[73,126],[72,127],[71,128],[70,129],[69,130],[68,131],[67,132],[66,133],[65,134],[64,135],[63,136],[62,137],[61,138],[60,139],[59,140],[58,141],[57,142],[56,143],[55,144],[54,145],[53,146],[52,147],[51,148],[50,149],[49,150],[48,151],[47,152],[46,153],[45,154],[44,155],[43,156],[42,157],[41,158],[40,159],[39,160],[38,161],[37,162],[36,163],[35,164],[34,165],[33,166],[32,167],[31,168],[30,169],[29,170],[28,171],[27,172],[26,173],[25,174],[24,175],[23,176],[22,177],[21,178],[20,179],[19,180],[18,181],[17,182],[16,183],[15,184],[14,185],[13,186],[12,187],[11,188],[10,189],[9,190],[8,191],[7,192],[6,193],[5,194],[4,195],[3,196],[2,197],[1,198],[0,199]]
[198,0]
[999999,999999]