[白俊-10026]赤い薬水

39263 ワード
BFS/DFS テキストリンク

質問する


リンク

コード#コード#


コードを作成し、赤緑薬人と非人が見た領域数を一度に計算します.
問題の例題や他の人がアップロードした反例を回しても正解と表示されますが、提出すると9%失敗したので、単独で計算して正解でした.
まずnの範囲は1~100なのであまり時間がかかりません
何が悪いんだ!!!!!!!!!!!!!!1

成功コード

from collections import deque
import sys
input = sys.stdin.readline

n =int(input())
graph = []

for _ in range(n) :
    graph.append(list(input()))

# 적록색약이 아닌 사람이 봤을 때 구역의 수
def count1() :
    visited = [[0] * n for _ in range(n)]
    tmp = ''
    count = 0
    for i in range(n) :
        for j in range(n) :
            queue = deque()
            if visited[i][j] == 0 :
                visited[i][j] = 1
                tmp = graph[i][j]
                # 초록이나 빨간색인 경우 하나의 문자로 바꿔준다.
                if graph[i][j] in ('G', 'R') :
                    graph[i][j] = 'G'
                queue.append([i, j])
                while queue :
                    p, q = queue.popleft()
                    for a, b in ([-1, 0], [1, 0], [0, 1], [0, -1]) :
                        if 0 <= p+a < n and 0 <= q+b < n :
                            if tmp == graph[p+a][q+b] and visited[p+a][q+b] == 0 :
                                visited[p+a][q+b] = 1
                                queue.append([p+a, q+b])
                                if tmp in ('G', 'R') :
                                    graph[p+a][q+b] = 'G'
                count += 1
    print(count, end=" ")

count1()

# 적록색약인 사람이 봤을 때 구역의 수
def count2() :
    visited = [[0] * n for _ in range(n)]
    tmp = ''
    count = 0
    for i in range(n) :
        for j in range(n) :
            queue = deque()
            if visited[i][j] == 0 :
                visited[i][j] = 1
                tmp = graph[i][j]
                queue.append([i, j])
                while queue :
                    p, q = queue.popleft()
                    for a, b in ([-1, 0], [1, 0], [0, 1], [0, -1]) :
                        if 0 <= p+a < n and 0 <= q+b < n :
                            if tmp == graph[p+a][q+b] and visited[p+a][q+b] == 0 :
                                visited[p+a][q+b] = 1
                                queue.append([p+a, q+b])
                count += 1
    print(count)

count2()
  • コード長が
    • 減少
    from collections import deque
import sys
input = sys.stdin.readline

n =int(input())
graph = []

for _ in range(n) :
    graph.append(list(input()))

def bfs(i, j) :
    queue = deque()
    visited[i][j] = 1
    tmp = graph[i][j]
    queue.append([i, j])
    while queue :
        p, q = queue.popleft()
        for a, b in ([-1, 0], [1, 0], [0, 1], [0, -1]) :
            if 0 <= p+a < n and 0 <= q+b < n :
                if tmp == graph[p+a][q+b] and visited[p+a][q+b] == 0 :
                    visited[p+a][q+b] = 1
                    queue.append([p+a, q+b])
                    if graph[p+a][q+b] == 'R' :
                        graph[p+a][q+b] = 'G'
    return 1
    
# 적록색약이 아닌 사람
visited = [[0] * n for _ in range(n)]
count = 0    
for i in range(n) :
    for j in range(n) :
        if visited[i][j] == 0 :
            count += bfs(i, j)
            if graph[i][j] == 'R' :
                graph[i][j] = 'G'
print(count, end=" ")        

# 적록색약인 사람
visited = [[0] * n for _ in range(n)]
count = 0    
for i in range(n) :
    for j in range(n) :
        if visited[i][j] == 0 :
            count += bfs(i, j)
print(count, end=" ")
    コード長が長すぎるため,dfsを1つに合成した.

    失敗コード

    from collections import deque
import sys
input = sys.stdin.readline

n =int(input())
graph = []
visited = [[0] * n for _ in range(n)]

for _ in range(n) :
    graph.append(list(input()))

# 1번이 적록색약이 아닌 사람, 2번은 적록색약인 사람
count_1 = 0
count_2 = 0
tmp = ''
for i in range(n) :
    for j in range(n) :
        if visited[i][j] == 0 :
            visited[i][j] = 1
            tmp = graph[i][j]
            # 적록색약인 경우에만
            # R, G일 때, 이미 방문했던 구역이 R, G이라면 1을 빼준다.
            if graph[i][j] in ('R', 'G') :
                for x, y in ([-1, 0], [1, 0], [0, 1], [0, -1]) : 
                    if 0 <= i+x < n and 0 <= j+y < n :
                        if graph[i+x][j+y] in ('R', 'G') and visited[i+x][j+y] == 1 :
                            count_2 -= 1
                            break
            queue = deque()
            queue.append([i, j])
            while queue :
                p, q = queue.popleft()
                for a, b in ([-1, 0], [1, 0], [0, 1], [0, -1]) :
                    if 0 <= p+a < n and 0 <= q+b < n :
                        if tmp == graph[p+a][q+b] and visited[p+a][q+b] == 0 :
                            visited[p+a][q+b] = 1
                            queue.append([p+a, q+b])
            count_1 += 1
            count_2 += 1
            print(count_1, count_2)
print(str(count_1), str(count_2))
    他の人のコードを見て、ほとんどの人はdfsを2回使って解読しました.
    この問題はもともとこのように解答したのでスキップしたと思います~~
    webpack
    Control.InvokeとControl.BeginInvoke