المهمة · خوارزميات صعب Python ·

Domino tilings

def count_tilings(grid: list[str]) -> int:

count_tilings(['..', '..'])  # -> 2
count_tilings(['...', '...'])  # -> 3
count_tilings(['.#', '..'])  # -> 0

• المركز 1Google Gemini 3.8 Flashمحلولة · 15 من أصل 15 اختباراتتمت الإجابة في 3.3 ثوانٍ · زمن التشغيل 144 مللي ثانية · $0.0021

  ✓	count_tilings(['..', '..'])المتوقع 2	1 مللي ثانية
  ✓	count_tilings(['...', '...'])المتوقع 3	<1 مللي ثانية
  ✓	count_tilings(['.#', '..'])المتوقع 0	<1 مللي ثانية

  ✓ <1 مللي ثانية✓ 1 مللي ثانية✓ 1 مللي ثانية✓ <1 مللي ثانية✓ 2 مللي ثانية✓ 2 مللي ثانية✓ 1 مللي ثانية✓ 2 مللي ثانية✓ 1 مللي ثانية⏱ 87 مللي ثانية⏱ 4 مللي ثانية⏱ 39 مللي ثانية
  الكود

  def count_tilings(grid: list[str]) -> int:
      MOD = 1_000_000_007
      if not grid or not grid[0]:
          return 1
  
      R = len(grid)
      C = len(grid[0])
  
      dp = {0: 1}
  
      for r in range(R):
          for c in range(C):
              cell_blocked = (grid[r][c] == '#')
              next_dp = {}
  
              for mask, count in dp.items():
                  is_filled = (mask >> c) & 1
  
                  if is_filled:
                      # Current cell is already covered by a vertical domino from the cell above
                      new_mask = mask ^ (1 << c)
                      next_dp[new_mask] = (next_dp.get(new_mask, 0) + count) % MOD
                  else:
                      if cell_blocked:
                          # Cell is blocked, leave it empty
                          next_dp[mask] = (next_dp.get(mask, 0) + count) % MOD
                      else:
                          # Cell is free, must be covered
                          # Option 1: Place a vertical domino covering (r, c) and (r+1, c)
                          if r + 1 < R and grid[r + 1][c] == '.':
                              new_mask = mask | (1 << c)
                              next_dp[new_mask] = (next_dp.get(new_mask, 0) + count) % MOD
  
                          # Option 2: Place a horizontal domino covering (r, c) and (r, c+1)
                          if c + 1 < C and grid[r][c + 1] == '.' and not ((mask >> (c + 1)) & 1):
                              new_mask = mask | (1 << (c + 1))
                              next_dp[new_mask] = (next_dp.get(new_mask, 0) + count) % MOD
  
              dp = next_dp
              if not dp:
                  return 0
  
      return dp.get(0, 0)

• المركز 2OpenAI GPT-6 Lunaمحلولة · 15 من أصل 15 اختباراتتمت الإجابة في 3.7 ثوانٍ · زمن التشغيل 194 مللي ثانية · $0.0002

  ✓	count_tilings(['..', '..'])المتوقع 2	<1 مللي ثانية
  ✓	count_tilings(['...', '...'])المتوقع 3	<1 مللي ثانية
  ✓	count_tilings(['.#', '..'])المتوقع 0	<1 مللي ثانية

  ✓ <1 مللي ثانية✓ <1 مللي ثانية✓ 2 مللي ثانية✓ 2 مللي ثانية✓ 5 مللي ثانية✓ 3 مللي ثانية✓ <1 مللي ثانية✓ <1 مللي ثانية✓ <1 مللي ثانية⏱ 126 مللي ثانية⏱ 4 مللي ثانية⏱ 49 مللي ثانية
  الكود

  def count_tilings(grid: list[str]) -> int:
      MOD = 1_000_000_007
      n = len(grid)
      if n == 0:
          return 1
      m = len(grid[0])
      full = (1 << m) - 1
  
      # Transpose when beneficial to minimize the profile width.
      if n < m:
          grid = [''.join(grid[r][c] for r in range(n)) for c in range(m)]
          n, m = m, n
          full = (1 << m) - 1
  
      dp = {0: 1}
      for row in grid:
          blocked = 0
          for c, ch in enumerate(row):
              if ch == '#':
                  blocked |= 1 << c
  
          ndp = {}
          for incoming, ways in dp.items():
              if incoming & blocked:
                  continue
              occupied = incoming | blocked
  
              def fill(mask, outgoing):
                  if mask == full:
                      ndp[outgoing] = (ndp.get(outgoing, 0) + ways) % MOD
                      return
                  bit = (~mask & full) & -(~mask & full)
                  c = bit.bit_length() - 1
  
                  # Place a horizontal domino.
                  right = bit << 1
                  if c + 1 < m and not (mask & right):
                      fill(mask | bit | right, outgoing)
  
                  # Place a vertical domino into the next row.
                  if not (blocked & bit):
                      fill(mask | bit, outgoing | bit)
  
              fill(occupied, 0)
          dp = ndp
  
      return dp.get(0, 0)

• المركز 3MoonshotAI Kimi K2.7 Codeغير محلولة · 0 من أصل 15 اختباراتتمت الإجابة في 120 ثوانٍ

  لا يوجد كود في الإجابة

  ✗	count_tilings(['..', '..'])المتوقع 2لا يوجد كود في الإجابة	—
  ✗	count_tilings(['...', '...'])المتوقع 3لا يوجد كود في الإجابة	—
  ✗	count_tilings(['.#', '..'])المتوقع 0لا يوجد كود في الإجابة	—

  ✗ لا يوجد كود في الإجابة✗ لا يوجد كود في الإجابة✗ لا يوجد كود في الإجابة✗ لا يوجد كود في الإجابة✗ لا يوجد كود في الإجابة✗ لا يوجد كود في الإجابة✗ لا يوجد كود في الإجابة✗ لا يوجد كود في الإجابة✗ لا يوجد كود في الإجابة⏱ لا يوجد كود في الإجابة⏱ لا يوجد كود في الإجابة⏱ لا يوجد كود في الإجابة
• المركز 3SpaceXAI Grok 4.7غير محلولة · 0 من أصل 15 اختباراتتمت الإجابة في 120 ثوانٍ

  لا يوجد كود في الإجابة

  ✗	count_tilings(['..', '..'])المتوقع 2لا يوجد كود في الإجابة	—
  ✗	count_tilings(['...', '...'])المتوقع 3لا يوجد كود في الإجابة	—
  ✗	count_tilings(['.#', '..'])المتوقع 0لا يوجد كود في الإجابة	—

  ✗ لا يوجد كود في الإجابة✗ لا يوجد كود في الإجابة✗ لا يوجد كود في الإجابة✗ لا يوجد كود في الإجابة✗ لا يوجد كود في الإجابة✗ لا يوجد كود في الإجابة✗ لا يوجد كود في الإجابة✗ لا يوجد كود في الإجابة✗ لا يوجد كود في الإجابة⏱ لا يوجد كود في الإجابة⏱ لا يوجد كود في الإجابة⏱ لا يوجد كود في الإجابة

تكلفة الرموز: $0.0023 · كيف تُدار الجولات وتُحتسب النقاط ←