22514번 - Rose Garden Witch 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 13 | 6 | 6 | 54.545% |
문제
薔薇園の魔女 GERTRUD は幅 W メートル，高さ H メートルの長方形の庭でバラを育てている．庭は一辺 1 メートルの正方形で区切られており，W×H のブロックに分けられている．各ブロックはバラが育てられているか育てられていないかのどちらかである．
ただ驚くべきことに，この庭で育てられているバラはブロックを越えて絡み合い 1 つの生命体となっている．この生命体は辺を共有しているブロック間を越えて絡み合うことができ，どこかある 1 点を共有していれば同じ生命体となる．
巴マミは庭の左下の角から直線に必殺技「ティロ・フィナーレ」で巨大な銃を撃ち，その弾丸が通る直線上でその生命体を分割した時，生命体が出来る限り多くの分割数に分断されるようにすることによりダメージを与えたい．ティロ・フィナーレは最大でこの生物を何分割できるか求めよ．
입력
入力は以下の形式で与えられる．
H W f11f12…f1W f21f22…f2W … fH1fH2…fHW
H は庭の高さ，W は庭の幅を表す．
fij は庭の各ブロックを表す文字であり，上から i 行目，左から j 列目のブロックの状態を表す．ブロックにバラが育てられている場合は fij は '#' となり，そうでない場合は '.' となる．
출력
生命体を直線で分割する時に，最大でいくつの部分に分割できるかを1行で出力せよ．
제한
- 1≤H≤600
- 1≤W≤600
- fijは
'#','.'のいずれかである． - 少なくとも 1 つはfij=
'#'となるマス fij が存在する． - 2 つのブロックが辺を共有するとき，それらは隣接していると呼ぶことにする．任意の 2 つの異なる
'#'のブロック fA,fB に対して，fA から隣接している'#'のブロックを辿っていって fB に着くことができる．(すなわち，薔薇のブロックは連結である．) - 入力中で 1 行目の行，H 行目の行，1 列目の列，または W 列目の列にあるブロックを盤面の端のブロックと呼ぶことにする．任意の
'.'のブロック fC に対して，fC から隣接している'.'のブロックを辿っていって，ある'.'の盤面の端のブロックに着くことができる．(すなわち，入力に"空洞"のブロックは存在しない．)
예제 입력 1
3 5 ##..# #..## ####.
예제 출력 1
4
このとき以下のように 4 つの部分に分割することができる．
예제 입력 2
3 3 #.# ### #.#
예제 출력 2
3
예제 입력 3
10 9 ......... ......... ####..... #..#.##.. #..#..#.. #..##.### #..##...# ##..##.## ###.#..#. ###.####.
예제 출력 3
6
예제 입력 4
10 11 ########### #.#.#.#.#.# #.#.#.#.#.# #.#.#.#.#.# #.#.#.#.#.# #.#.#.#.#.# #.#.#.#.#.# #.#.#.#.#.# #.#.#.#.#.# #.#.#.#.#.#
예제 출력 4
7
예제 입력 5
25 38 ...........#...............#.......... ...........###..........####.......... ...........#####.......####........... ............###############........... ............###############........... ............##############............ .............#############............ ............###############........... ...........#################.......... .......#...#################...#...... .......##.##################..##...... ........####################.##....... ..........####################........ .........#####..########..#####....... .......######....#####....######...... ......########...#####..########.#.... ....#######..#...#####..#..########... ..#########.....#######......#######.. ...#######......#######........###.... ..####.........#########........###... ...............#########.............. ..............##########.............. ..............##########.............. ...............########............... ...............########...............
예제 출력 5
8
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호