We’ve updated our Terms of Service. A new AI Addendum clarifies how Stack Overflow utilizes AI interactions.

Return to Revisions

Python 3, (削除) 667 (削除ここまで) (削除) 554 (削除ここまで) (削除) 526 (削除ここまで) 471 bytes

-49 bytes thanks to @ovs and @pppery

C=eval(input())
N=next
E=enumerate
def F(x,y,f):
 try:1/-~x/-~y;global a,v,n;c=C[y][x];(x,y)in v<Q;n[c]+=1;c&f<1<Q;C[y][x]=0;v+=[(x,y)];a+=(c==15)+1;[c>>a&1and F(x+a%2*(2-a),y+(a-1&~a),1<<(a^2))for a in(0,1,2,3)]
 except:1
while l:=[(x,y)for y,r in E(C)for x,e in E(r)if e]:
 a=0;v=[];n={k:0for k in range(16)};F(*l[0],15);m,M=map(min,zip(*v)),map(max,zip(*v));(len(v)!=n[15]or(N(M)-N(m)+1)*(N(M)-N(m)+1)!=a/2)and(a!=4*n[6]*n[12]or n[6]!=n[9]or n[3]!=n[12]or n[0]>0)and z

Try it online! (all testcases)

Throws NameError for false and doesn't throw for true.

Golf notes:

• or has a higher precedence than and

Commented, Ungolfed

# bit order of a cell:
# truthy bit if that side is white(opeN)
# 0
# 3 1
# 2
# black: 0
# white: 15
# SE: 9
# SW: 3
# NW: 6
# NE: 12
# helper function to flood fill starting at (x,y)
# passes x,y position
# passes down mutable values
 # visited: array of coordinates visited
 # num_visited: dict counting how many of each cell type have been visited
def flood_solve(case, x, y, coming_from):
 global touched0, white_area, visited, num_visited
 # if out-of-bounds in the positive direction, this will throw
 try: c = case[y][x]
 except: return
 if (x,y) in visited: return
 # maybe can include touched0 into num_visited dict, then del num_visited[0] later
 # Keep track if the white region touches a full-black cell (0)
 touched0 = touched0 or c == 0
 # Check if this new cell is white on the side of the previous cell
 if not c & coming_from: return
 # Turn all visited cells to 0 to avoid flood-filling the same region
 case[y][x] = 0
 # Keep track of which cells are visited
 visited += [(x,y)]
 # Keep track of the counts of NE,NW,SE,and SW cells (3,6,9,12)
 num_visited[c] += 1
 # Keep track of the area of cells visited (1 for full-white, 0.5 for all else)
 if c != 15:
 white_area += 0.5
 else:
 white_area += 1
 # Flood recurse in each direction
 # Call flood_solve on (x,y-1) if (x,y) is white on its top side
 # Whether (x,y-1) is white on its bottom side is determined using coming_from
 if c & 1 and y>0: flood_solve(case, x, y-1, 4)
 if c & 2: flood_solve(case, x+1, y, 8)
 if c & 4: flood_solve(case, x, y+1, 1)
 if c & 8 and x>0: flood_solve(case, x-1, y, 2)
 return(visited, num_visited)
def solve(case):
 global touched0, white_area, visited, num_visited
 touched0 = False
 white_area = 0
 visited = []
 num_visited = {3:0,6:0,9:0,12:0,15:0}
 # Pick a cell with white
 for y,row in enumerate(case):
 for x,e in enumerate(row):
 if e > 0:
 # Floodfill whites from it
 # Pass 15 (0b1111) as coming_from since (x,y) can always be reached
 # Pass case mutably
 visited, num_visited = flood_solve(case, x, y, 15); break
 # (Maybe rectangular checks can be moved here to avoid looping by re-calling solve)
 # flooding always visits at least one cell, so visited is equivalent to the proposition
 # "A cell containing some white has already been found"
 if visited: break
 # Base case: if no white remains, then return True
 if not visited:
 return True
 v = list(zip(*visited))
 # v = [list of x positions visited, list of y positions visited]
 top_left = list(map(min, v))
 bottom_right = list(map(max, v))
 # If only entered all-white cells and area of bounding box of cells entered == area of cells entered:
 if len(visited)==num_visited[15] and (bottom_right[1] - top_left[1] + 1) * (bottom_right[0] - top_left[0] + 1) == white_area:
 # looks like an infinite recursion, but visited cells are replaced with 0 in flood_solve
 return solve(case)
 # If touched an all-black cell, can't be an angled rectangle, since angled rectangles only have angled sides
 if touched0:
 return
 n = num_visited
 # Should have #(NW entered)=#(SE entered) and #(NE)=#(SW)
 # (is this check redundant with the next area check? Maybe the area check can be rearranged by using area<=2*(perimeter/2)^?)
 if not n[6] == n[9] or not n[3] == n[12]:
 return
 if 2*n[6]*n[12] == white_area:
 # Success! it's an angled rectangle
 return solve(case)

Pseudo-code algorithm

• Start
• Pick a cell with white; floodfill whites from it
  • (Base case: if no white remains, then return True)
  • While floodfilling:
    • Keep track of which cells are visited
    • Keep track of the counts of cells
    • Keep track if the white region touches a full-black cell (0)
    • Keep track of the area of cells visited (1 for full-white, 0.5 for all else)
    • Turn all visited cells to 0 to avoid flood-filling the same region
• If only entered all-white cells and area of bounding box of cells entered == area of cells entered:
  • Success! it's an upright rectangle.
  • GOTO Start; use the updated case (all visited cells turned black)
• If touched an all-black cell
  • Can't be an angled rectangle, since angled rectangles only have angled sides
  • return False
• Should have #(NW enetered)=#(SE entered) and #(NE)=#(SW) (is this check redundant with the next area check?)
• Each NW cell contributes sqrt(2) to the length of the NW side of the rectangle
• Each NE cell contributes sqrt(2) to the length of the NE side of the rectangle
• If area == 2*#(NW)*#(NE):
  • Success! it's an angled rectangle
  • GOTO Start; use the updated case (all visited cells turned black) White region filled can't be angled or upright rectangle anymore return False