def solve(): height, width = map(int, input().split()) floor = [] didVisit = [[False] * width for _ in range(height)] enterance = [] # height * 1000 + width doors = set() openableDoors = set() result = 0 for _ in range(height): floor.append(list(input())) heldKeys = input() if heldKeys != '0' : for key in list(heldKeys): openableDoors.add(key.upper()) # find starting points for x in range(height): for y in range(width): if floor[x][y] == '*': didVisit[x][y] = True elif x == 0 or x == height - 1 or y == 0 or y == width - 1: if floor[x][y] == '.': enterance.append([x, y]) elif floor[x][y] == '$': result += 1 enterance.append([x,y]) floor[x][y] = '.' elif 'a' <= floor[x][y] <= 'z' : openableDoors.add(floor[x][y].upper()) enterance.append([x,y]) floor[x][y] = '.' elif 'A' <= floor[x][y] <='Z' and floor[x][y] in openableDoors: enterance.append([x,y]) floor[x][y] = '.' elif 'A' <= floor[x][y] <='Z': doorLoc = x * 1000 + y doors.add(doorLoc) for x in range(height): for y in range(width): if (x == 0 or x == height - 1 or y == 0 or y == width - 1) and ('A' <= floor[x][y] <='Z' and floor[x][y] in openableDoors): enterance.append([x,y]) floor[x][y] = '.' else: continue startIndex = 0 endIndex = len(enterance) directions = [[1,0],[0,1],[-1,0], [0,-1]] while startIndex < endIndex: x, y = enterance[startIndex] startIndex += 1 didVisit[x][y] = True for dx, dy in directions: newx = x + dx newy = y + dy if not (0 <= newx < height and 0 <= newy < width) or didVisit[newx][newy]: continue if floor[newx][newy] == '.': enterance.append([newx, newy]) endIndex += 1 elif floor[newx][newy] == '$': result += 1 enterance.append([newx, newy]) endIndex += 1 floor[newx][newy] = '.' elif 'a' <= floor[newx][newy] <= 'z' : openableDoors.add(floor[newx][newy].upper()) enterance.append([newx, newy]) endIndex += 1 floor[newx][newy] = '.' elif 'A' <= floor[newx][newy] <='Z': doorLoc = newx * 1000 + newy doors.add(doorLoc) newDoors = True newKeys = True while newDoors or newKeys: newDoors = False newKeys = False addDoors = set() removeDoor = set() for door in doors: doorx, doory = door // 1000, door % 1000 if floor[doorx][doory] in openableDoors: removeDoor.add(door) floor[doorx][doory] = '.' doorStart = 0 doorEnd = 1 doorway = [[doorx, doory]] while doorStart < doorEnd: x, y = doorway[doorStart] doorStart += 1 didVisit[x][y] = True for dx, dy in directions: newx = x + dx newy = y + dy if not ((0 <= newx < height) and (0 <= newy < width)) or didVisit[newx][newy]: continue if floor[newx][newy] == '.': doorway.append([newx, newy]) doorEnd += 1 elif floor[newx][newy] == '$': result += 1 doorway.append([newx, newy]) doorEnd += 1 floor[newx][newy] = '.' elif 'a' <= floor[newx][newy] <= 'z' : openableDoors.add(floor[newx][newy].upper()) doorway.append([newx , newy]) doorEnd += 1 floor[newx][newy] = '.' newKeys = True elif 'A' <= floor[newx][newy] <='Z': loc = newx * width + newy addDoors.add(loc) newDoors = True doors = doors-removeDoor doors &= addDoors # debugging print(result) def main(): testcase = int(input()) for _ in range(testcase): solve() main()

제출 #135709

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: