USACO the castle

제목 번역
묘사 하 다.
우리 의 어수룩 한 USACO 주인공 농부 존 (Farmer John) 은 상상 할 수 없 는 운 으로 그의 생일 날 특별한 선물 을 받 았 다. '행운 의 아일랜드' (복권).결국 이 복권 은 그 에 게 이번 경기 의 유일한 상품 인 아일랜드 교외 에 자리 잡 은 환상 적 인 성 을 주 었 다!
자랑 하 기 를 좋아 하 는 농부 존 은 곧 전통 을 자랑 하 는 웨 스 콘 신 고향 으로 돌아 가 자랑 하기 시작 했다. 농부 존 은 젖소 들 에 게 그의 성에 관 한 모든 것 을 알려 주 고 싶 어 했다.그 는 성 안에 방 이 몇 개 있 는 지, 방 마다 얼마나 큰 지 알 기 위해 허풍 을 떨 기 전의 준 비 를 해 야 한다.또 농부 존 은 더 큰 방 을 만 들 기 위해 단독 벽 (두 단위 간 의 벽 을 가리 키 는 말) 을 뜯 어 내 려 고 한다.너의 일 은 농부 존 을 도와 이상 의 준 비 를 해서 방 의 수 와 방 의 크기 를 계산 하 는 것 이다.
성의 평면 도 는 M * N (1 < = M, N < = 50) 개의 정사각형 단위 로 나 뉘 어 져 있 으 며, 이러한 단 위 는 0 에서 4 면 벽 으로 둘러싸 여 있다. 성 주 위 는 반드시 외 벽 으로 둘러싸 여 바람 과 비 를 막 을 수 있다. (평면도 의 주 위 는 반드시 벽 이다.)
아래 에 주석 이 있 는 성 평면 도 를 자세히 연구 하 세 요.

    1   2   3   4   5   6   7

  #############################

1 #   |   #   |   #   |   |   #

  #####---#####---#---#####---#   

2 #   #   |   #   #   #   #   #

  #---#####---#####---#####---#

3 #   |   |   #   #   #   #   #   

  #---#########---#####---#---#

4 # ->#   |   |   |   |   #   #   

  #############################

 

# =      -,| =     

-> =     ，                   

우정 힌트, 이 성의 평면도 는 7×4 개의 단위 입 니 다. 하나의 '방' 은 평면도 에 있 는 '\ #', '-', '|' 으로 둘러싸 인 칸 입 니 다. 예 를 들 어 이 사례 는 5 개의 방 이 있 습 니 다. (크기 는 각각 9, 7, 3, 1, 8 개의 단위 (순위 가 앞 뒤 를 가리 지 않 음)
화살표 가 가리 키 는 벽 을 옮 기 면 두 개의 방 을 새 방 으로 합 칠 수 있 고 다른 벽 으로 옮 겨 서 형 성 된 방 보다 크다. (원문: Removing the wall marked by the arrow merges a pair of rooms to make the largest possible room that can be made by remoting a single wall.)
성 은 적어도 두 개의 방 이 있 고 벽 이 옮 겨 갈 수 있 을 것 이 라 고 보장 한다.
격식.
PROGRAM NAME: castle
INPUT FORMAT: 첫 번 째 줄 에는 두 개의 정수 가 있 습 니 다. M 과 N 성의 평면 도 는 숫자 로 구 성 된 행렬 로 표시 하고 한 숫자 는 한 단 위 를 표시 하 며 행렬 은 N 줄 M 열 이 있 습 니 다. 입력 은 샘플 의 그림 과 일치 합 니 다.
각 단위 의 숫자 는 우리 에 게 이 단위 의 동서남북 에 벽 이 존재 하 는 지 를 알려 준다. 모든 숫자 는 아래 네 개의 정수 중 하나 또는 몇 개 또는 하나 도 더 하지 않 은 것 이다.

1:      

2:      

4:      

8:      

성 내부 의 벽 은 두 번 규정 된다. 예 를 들 어 (1, 1) 남쪽의 벽 도 (2, 1) 북쪽 의 벽 으로 표시 된다.
OUTPUT FORMAT:
(file castle.out)
출력 은 다음 4 줄 을 포함 합 니 다:
제1 행: 성의 방 수.
두 번 째 줄: 가장 큰 방 의 크기
세 번 째 줄: 벽 을 제거 하면 얻 을 수 있 는 가장 큰 방 의 크기
네 번 째 줄: 어느 벽 을 제거 하면 면적 이 가장 큰 새 방 을 얻 을 수 있 습 니까?
가장 좋 은 벽 을 선택 하여 무 너 뜨 립 니 다. 얼마나 풀 었 을 때 가장 서쪽 에 있 는 것 을 선택 하고, 여전히 얼마나 풀 었 을 때 가장 남쪽 에 있 는 것 을 선택 하 십시오. 같은 칸 의 북쪽 벽 은 동쪽 벽 보다 더 우선 합 니 다.
이 벽의 남쪽 이웃 단위 의 북 벽 이나 서쪽 이웃 단위 의 동 벽 으로 이 벽 을 표시 하 는데 방법 은 이웃 단위 의 행 수, 열 수 와 벽의 방위 ('N' (북) 또는 'E' (동) 를 수출 하 는 것 이다.
SAMPLE INPUT

7 4

11 6 11 6 3 10 6

7 9 6 13 5 15 5

1 10 12 7 13 7 5

13 11 10 8 10 12 13

SAMPLE OUTPUT

5

9

16

4 1 E

해제
usaco 중 순위 http://www.nocow.cn/index.php/Translate:USACO/castle 뒷전 틀림없이 Flood Fill Algorithms 을 썼 을 것 이다.

 1 {

 2 ID:fuzhong2

 3 PROG:castle

 4 LANG:PASCAL

 5 }

 6 var

 7   num,c,d:array[1..50,1..50]of longint;

 8   f:array[0..51,0..51,1..4]of boolean;

 9   m,n,i,j:longint;

10 procedure pw;

11   var

12     te:array[1..4] of longint = (1,2,4,8);

13     i,j,k:longint;

14   begin

15     for i:=1 to n do

16       for j:= 1 to m do

17         for k:= 4 downto 1 do

18           if num[i,j]>=te[k] then begin f[i,j,k]:=false; dec(num[i,j],te[k]); end;

19   end;

20 procedure work1;

21   var

22     maxc,co,i,j,x,k,l:longint;

23   procedure dfs(i,j,co:longint;var x:longint);

24     var

25       y:longint;

26     begin

27       if (f[i,j,1]) and (c[i,j-1]=0) then begin c[i,j-1]:=co;  inc(x); dfs(i,j-1,co,x); end;

28       if (f[i,j,2]) and (c[i-1,j]=0) then begin c[i-1,j]:=co;  inc(x); dfs(i-1,j,co,x); end;

29       if (f[i,j,3]) and (c[i,j+1]=0) then begin c[i,j+1]:=co;  inc(x); dfs(i,j+1,co,x); end;

30       if (f[i,j,4]) and (c[i+1,j]=0) then begin c[i+1,j]:=co;  inc(x); dfs(i+1,j,co,x); end;

31     end;

32   begin

33     co:=0;

34     fillchar(c,sizeof(c),0);

35     maxc:=-1;

36     for i:=1 to n do

37       for j:= 1 to m do

38         if c[i,j]=0 then

39         begin

40           x:=1;

41           inc(co);

42           c[i,j]:=co;

43           dfs(i,j,co,x);

44             for k:=1 to n do

45               for l:= 1 to m do

46                 if c[k,l]=co then d[k,l]:=x;

47           if x>maxc then maxc:=x;

48         end;

49     writeln(co);

50     writeln(maxc);

51   end;

52   procedure work2;

53     var

54       temp:array[1..2,1..2]  of longint= ((-1,0),(0,1));

55       mi,mj,maxs,nk,i,j,k:longint;

56     begin

57       maxs:=-1;

58       for j:=m downto 1 do

59       for i:= 1 to n do

60       for k:=2 downto 1  do

61               if (i+temp[k,1]>=1) and(j+temp[k,2]<=m) then

62           begin

63               if (not (c[i,j]=c[i+temp[k,1],j+temp[k,2]]))and(maxs<=d[i,j]+d[i+temp[k,1],j+temp[k,2]]) then

64               begin

65                 mi:=i;

66                 mj:=j;

67                 maxs:=d[i,j]+d[i+temp[k,1],j+temp[k,2]];

68                 nk:=k;

69               end;

70               end;

71      writeln(maxs);

72      write(mi,' ',mj,' ');

73      if nk=1 then writeln('N') else writeln('E');

74     end;

75 begin

76   assign(input,'castle.in');reset(input);

77   assign(output,'castle.out');rewrite(output);

78   fillchar(f,sizeof(f),true);

79   read(m,n);

80   for i:= 1 to n do

81     for j:=1 to m do

82       read(num[i,j]);

83   pw;

84   work1;

85 {  for i:= 1 to n do  //          

86      begin

87     for j:=1 to m do

88      write(d[i,j],' ');

89      writeln;

90      end;  }

91      work2;

92   close(input);

93   close(output);

94 end.

USER: fu zhongqing [fuzhong2]

TASK: castle

LANG: PASCAL



Compiling...

Compile: OK



Executing...

   Test 1: TEST OK [0.000 secs, 316 KB]

   Test 2: TEST OK [0.000 secs, 316 KB]

   Test 3: TEST OK [0.000 secs, 316 KB]

   Test 4: TEST OK [0.000 secs, 316 KB]

   Test 5: TEST OK [0.000 secs, 316 KB]

   Test 6: TEST OK [0.000 secs, 316 KB]

   Test 7: TEST OK [0.032 secs, 316 KB]

   Test 8: TEST OK [0.000 secs, 316 KB]



All tests OK.

Your program ('castle') produced all correct answers! This is your submission #17 for this problem. Congratulations!  
(토로: 17 번,,,,, 후 두 동서남북 어디 에 한 시간 동안 갈등 이 있 었 습 니까?)