fork download
  1. import sys
  2. from collections import defaultdict
  3.  
  4. # Constants
  5. MOD = int(1e9 + 7)
  6.  
  7. # Game state tracking
  8. game_grid = []
  9. state_map = defaultdict(int)
  10. column_depth = [0] * 7 # Track the fill depth of each column
  11.  
  12. # Check for a 4-in-a-row pattern starting from a specific cell
  13. def check_sequence(start_row, start_col, row_step, col_step, player):
  14. for i in range(4):
  15. row = start_row + i * row_step
  16. col = start_col + i * col_step
  17. if column_depth[col] > row or game_grid[row][col] != player:
  18. return False
  19. return True
  20.  
  21. # Count the number of "4-in-a-row" sequences for both players ('F' and 'C')
  22. def count_sequences():
  23. rows = len(game_grid)
  24. cols = len(game_grid[0])
  25. player_f_count = 0
  26. player_c_count = 0
  27.  
  28. for row in range(rows):
  29. for col in range(cols):
  30. if col + 3 < cols: # Horizontal
  31. player_f_count += check_sequence(row, col, 0, 1, 'F')
  32. player_c_count += check_sequence(row, col, 0, 1, 'C')
  33. if row + 3 < rows: # Vertical
  34. player_f_count += check_sequence(row, col, 1, 0, 'F')
  35. player_c_count += check_sequence(row, col, 1, 0, 'C')
  36. if row + 3 < rows and col + 3 < cols: # Diagonal down-right
  37. player_f_count += check_sequence(row, col, 1, 1, 'F')
  38. player_c_count += check_sequence(row, col, 1, 1, 'C')
  39. if row + 3 < rows and col - 3 >= 0: # Diagonal down-left
  40. player_f_count += check_sequence(row, col, 1, -1, 'F')
  41. player_c_count += check_sequence(row, col, 1, -1, 'C')
  42.  
  43. # Stop counting early if both players have sequences
  44. if player_f_count > 0 and player_c_count > 0:
  45. return player_f_count, player_c_count
  46. return player_f_count, player_c_count
  47.  
  48. # Recursive function to simulate the game and determine the result
  49. def simulate_game(turn):
  50. game_state = ''.join(map(str, column_depth))
  51.  
  52. if game_state in state_map:
  53. return state_map[game_state]
  54.  
  55. f_seq, c_seq = count_sequences()
  56.  
  57. if f_seq == 0 and c_seq == 0:
  58. state_map[game_state] = 0
  59. elif f_seq > 0 and c_seq == 0:
  60. state_map[game_state] = 1
  61. elif f_seq == 0 and c_seq > 0:
  62. state_map[game_state] = -1
  63. else:
  64. current_player = 'F' if turn == 1 else 'C'
  65. result = 0
  66.  
  67. for col in range(7):
  68. if column_depth[col] < len(game_grid) and game_grid[column_depth[col]][col] == current_player:
  69. column_depth[col] += 1
  70. opponent_result = simulate_game(1 - turn)
  71. column_depth[col] -= 1
  72.  
  73. if opponent_result == 0:
  74. continue
  75. elif opponent_result == 1:
  76. result = max(result, 1)
  77. elif opponent_result == -1:
  78. result = min(result, -1)
  79.  
  80. state_map[game_state] = result
  81. return state_map[game_state]
  82.  
  83. # Handle input and process each test case
  84. def process_case():
  85. global game_grid, column_depth, state_map
  86. state_map.clear()
  87. column_depth = [0] * 7 # Reset column depths
  88. game_grid = [input().strip() for _ in range(6)] # Read the 6x7 grid
  89. return simulate_game(1)
  90.  
  91. # Main function to drive the program
  92. if __name__ == "__main__":
  93. input = sys.stdin.read
  94. data = input().splitlines()
  95.  
  96. test_cases = int(data[0])
  97. index = 1
  98.  
  99. for case_num in range(1, test_cases + 1):
  100. game_grid = data[index:index + 6]
  101. index += 6
  102.  
  103. print(f"Case #{case_num}: ", end="")
  104. result = process_case()
  105.  
  106. if result == 1:
  107. print("F")
  108. elif result == -1:
  109. print("C")
  110. elif result == 0:
  111. print("0")
  112. else:
  113. print("?")
  114.  
Success #stdin #stdout 0.03s 9928KB
stdin
115

FFFFFFF
CCCCCCC
FFFFFFF
CCCCCCC
FFFFFFF
CCCCCCC

FCFCFCF
FCCFCFC
CFFCFCF
CFCFCFC
CFCFFCF
CFCFCFC

FCFCFCF
CCFCFCF
CFCFCCF
CFFFCFC
FCCCCCC
CFFFFFF

FCFCFCF
CFCFCFC
FCFCFCF
FCFCFCF
CFCFCFC
CFCFCFC

FFFFCFF
CCCCCFF
FCFCFFC
CCFCFCF
FFCCCFC
FCCFFCC

FFCCFCF
CCCFFFF
FFCCFFC
CFFFFCC
stdout
Case #1: 0
Case #2: 0
Case #3: 0
Case #4: 0
Case #5: 0
Case #6: 0
Case #7: 0
Case #8: 0
Case #9: 0
Case #10: 0
Case #11: 0
Case #12: 0
Case #13: 0
Case #14: 0
Case #15: 0
Case #16: 0
Case #17: 0
Case #18: 0
Case #19: 0
Case #20: 0
Case #21: 0
Case #22: 0
Case #23: 0
Case #24: 0
Case #25: 0
Case #26: 0
Case #27: 0
Case #28: 0
Case #29: 0
Case #30: 0
Case #31: 0
Case #32: 0
Case #33: 0
Case #34: 0
Case #35: 0
Case #36: 0
Case #37: 0
Case #38: 0
Case #39: 0
Case #40: 0
Case #41: 0
Case #42: 0
Case #43: 0
Case #44: 0
Case #45: 0
Case #46: 0
Case #47: 0
Case #48: 0
Case #49: 0
Case #50: 0
Case #51: 0
Case #52: 0
Case #53: 0
Case #54: 0
Case #55: 0
Case #56: 0
Case #57: 0
Case #58: 0
Case #59: 0
Case #60: 0
Case #61: 0
Case #62: 0
Case #63: 0
Case #64: 0
Case #65: 0
Case #66: 0
Case #67: 0
Case #68: 0
Case #69: 0
Case #70: 0
Case #71: 0
Case #72: 0
Case #73: 0
Case #74: 0
Case #75: 0
Case #76: 0
Case #77: 0
Case #78: 0
Case #79: 0
Case #80: 0
Case #81: 0
Case #82: 0
Case #83: 0
Case #84: 0
Case #85: 0
Case #86: 0
Case #87: 0
Case #88: 0
Case #89: 0
Case #90: 0
Case #91: 0
Case #92: 0
Case #93: 0
Case #94: 0
Case #95: 0
Case #96: 0
Case #97: 0
Case #98: 0
Case #99: 0
Case #100: 0
Case #101: 0
Case #102: 0
Case #103: 0
Case #104: 0
Case #105: 0
Case #106: 0
Case #107: 0
Case #108: 0
Case #109: 0
Case #110: 0
Case #111: 0
Case #112: 0
Case #113: 0
Case #114: 0
Case #115: 0