늑대와 양

• 문제의 마지막 부분에 한번 더 강조하고 있지만, 최소 갯수로 울타리를 설치할 필요는 없다.
• 우선 늑대와 양이 인접한 칸에 위치한 경우에는 울타리로 둘을 분리할수 있다. 역으로 그렇게 위치한 부분이 없다면 울타리로 분리가 가능하다.
• 분리가 가능한 경우에 울타리를 설치하는 간단한 방법은 각 늑대의 주변 4칸에 울타리를 설치하면 늑대를 양으로부터 모두 분리시킬수 있다. 이것보다도 더욱 간단한 방법은. 그냥 모든 빈칸에 전부 울타리를 설치하는 것이다. 늑대와 양 모두 원래자리에서 한발짝도 움직일수 없지만 어쨌든 분리는 가능하다.
• 모든 인접한 칸에 대해서 늑대와 양이 같이 있는지 여부를 확인하는것은 O(R*C)가 걸린다. 모든 빈칸을 울타리로 바꾸는 것도 역시 O(R*C)이다.

"""Solution code for "BOJ 16956. 늑대와 양".

- Problem link: https://www.acmicpc.net/problem/16956
- Solution link: http://www.teferi.net/ps/problems/boj/16956

Tags: [Ad hoc]
"""

def main():
    R, C = [int(x) for x in input().split()]  # pylint: disable=unused-variable
    board = [input() for _ in range(R)]

    for row in board:
        if 'SW' in row or 'WS' in row:
            print('0')
            return
    for col in zip(*board):
        col = ''.join(col)
        if 'SW' in col or 'WS' in col:
            print('0')
            return

    print('1')
    print('\n'.join(row.replace('.', 'D') for row in board))


if __name__ == '__main__':
    main()