POJ 1164 The Castle
24745 ワード
住所:http://poj.org/problem?id=1164
質問説明:図1は城の地形図です.プログラムを作成してください.計算してください.
城は全部で何部屋ありますか.
一番大きい部屋はどのくらいですか.
城はm´n(m≦50,n≦50)個のブロックに分割され、各ブロックに0~4面の壁がある
入力:プログラムは標準入力装置からデータを読み込みます.
1行目は2つの整数で、それぞれ南北方向、東西方向のブロック数です.
次の入力行では、各ブロックは1つの数字(0≦p≦50)で記述される.四角い周囲の壁を1つの数字で表し、1は西壁、2は北壁、4は東壁、8は南壁を表す.
各ブロックは、その周囲の壁を表す数字の和で表されます.城の内壁は2回計算され、ブロック(1,1)の南壁はブロック(2,1)の北壁でもある.
入力されたデータは、城に少なくとも2つの部屋があることを保証します.
出力:城の部屋数、城の中で最大の部屋に含まれるブロック数.結果は標準出力装置に表示されます.
考え方1:
任意のブロック(i,j)に対して、入力記述ではpで表される
p<8
p (i,j)南の壁はなく,(i+1,j)と(i,j)は同じ部屋に属する
p(i+1,j)と同じ部屋に属するすべてのブロックも(i,j)と同じ部屋に属する
p%8<4
p (i,j)東の壁がなく、(i,j+1)と(i,j)は同じ部屋に属する
p(i,j+1)と同じ部屋に属するすべてのブロックも(i,j)と同じ部屋に属する
p%4<2
p(i,j)は北壁がなく,(i−1,j)と(i,j)は同じ部屋に属する
p(i-1,j)と同じ部屋に属するすべてのブロックも(i,j)と同じ部屋に属する
p%2=0
p (i,j)西壁がなく、(i,j-1)と(i,j)は同じ部屋に属する
p(i,j-1)と同じ部屋に属するすべてのブロックも(i,j)と同じ部屋に属する
テーマ: 部屋の数 和 部屋の最大面積.
構想2:デバッグが便利に見えるように壁を8で表し、通路を0で表し(もちろん部屋エリアも通れるので0で表す)、(2*row+1)*(2*column+1)の行列で表します(0≦i ≤ 2*row ,0 ≤ j ≦2*column)、i,jが奇数の場合、点(i,j)は部屋領域を表し、残りは壁またはドアである.
心得:こんなことがあるとは思わなかった.
3 33 2 61 0 49 8 12
デバッグの結果、部屋の領域は8ですが、途中は0で、計算が繰り返され、dfs()が変更されました.
while()にはこのroom[i][j]='0')が加わっている.この文を len++; 前面に出る.
転載:
質問説明:図1は城の地形図です.プログラムを作成してください.計算してください.
城は全部で何部屋ありますか.
一番大きい部屋はどのくらいですか.
城はm´n(m≦50,n≦50)個のブロックに分割され、各ブロックに0~4面の壁がある
入力:プログラムは標準入力装置からデータを読み込みます.
1行目は2つの整数で、それぞれ南北方向、東西方向のブロック数です.
次の入力行では、各ブロックは1つの数字(0≦p≦50)で記述される.四角い周囲の壁を1つの数字で表し、1は西壁、2は北壁、4は東壁、8は南壁を表す.
各ブロックは、その周囲の壁を表す数字の和で表されます.城の内壁は2回計算され、ブロック(1,1)の南壁はブロック(2,1)の北壁でもある.
入力されたデータは、城に少なくとも2つの部屋があることを保証します.
出力:城の部屋数、城の中で最大の部屋に含まれるブロック数.結果は標準出力装置に表示されます.
考え方1:
任意のブロック(i,j)に対して、入力記述ではpで表される
p<8
p (i,j)南の壁はなく,(i+1,j)と(i,j)は同じ部屋に属する
p(i+1,j)と同じ部屋に属するすべてのブロックも(i,j)と同じ部屋に属する
p%8<4
p (i,j)東の壁がなく、(i,j+1)と(i,j)は同じ部屋に属する
p(i,j+1)と同じ部屋に属するすべてのブロックも(i,j)と同じ部屋に属する
p%4<2
p(i,j)は北壁がなく,(i−1,j)と(i,j)は同じ部屋に属する
p(i-1,j)と同じ部屋に属するすべてのブロックも(i,j)と同じ部屋に属する
p%2=0
p (i,j)西壁がなく、(i,j-1)と(i,j)は同じ部屋に属する
p(i,j-1)と同じ部屋に属するすべてのブロックも(i,j)と同じ部屋に属する
テーマ: 部屋の数 和 部屋の最大面積.
構想2:デバッグが便利に見えるように壁を8で表し、通路を0で表し(もちろん部屋エリアも通れるので0で表す)、(2*row+1)*(2*column+1)の行列で表します(0≦i ≤ 2*row ,0 ≤ j ≦2*column)、i,jが奇数の場合、点(i,j)は部屋領域を表し、残りは壁またはドアである.
心得:こんなことがあるとは思わなかった.
3 33 2 61 0 49 8 12
デバッグの結果、部屋の領域は8ですが、途中は0で、計算が繰り返され、dfs()が変更されました.
while()にはこのroom[i][j]='0')が加わっている.この文を len++; 前面に出る.
1
2
3 #include<stdio.h>
4 #include<string.h>
5
6 int row, column, len;
7 char room[101][101];
8
9 void dfs(int i, int j)
10 {
11 while(i>=1 && i<=(row<<1) && j>=1 && j<=(column<<1) && room[i][j] == '0')
12 {
13 len++;
14 room[i][j] = '8';
15 if(room[i][j+1] == '0')
16 {
17 room[i][j+1] = '8';
18 dfs(i, j+2);
19 }
20 if(room[i+1][j] == '0')
21 {
22 room[i+1][j] = '8';
23 dfs(i+2, j);
24 }
25 if(room[i][j-1] == '0')
26 {
27 room[i][j-1] = '8';
28 dfs(i, j-2);
29 }
30 if(room[i-1][j] == '0')
31 {
32 room[i-1][j] = '8';
33 dfs(i-2, j);
34 }
35 }
36 }
37
38 int main()
39 {
40 int i, j, nRoom, max, num;
41 while(scanf("%d %d", &row, &column) != EOF)
42 {
43 for(i=0; i<=(row<<1); i++) //
44 for(j=0; j<=(column<<1); j++)
45 room[i][j] = '8'; //8 ，0
46
47 for(i=1; i<=(row<<1); i+=2) //
48 for(j=1; j<=(column<<1); j+=2)
49 {
50 scanf("%d", &num);
51 room[i][j] = '0';
52 if(!(num&1) && room[i][j-1] == '8') room[i][j-1] = '0';
53 if(!(num&2) && room[i-1][j] == '8') room[i-1][j] = '0';
54 if(!(num&4) && room[i][j+1] == '8') room[i][j+1] = '0';
55 if(!(num&8) && room[i+1][j] == '8') room[i+1][j] = '0';
56 }
57
58 max = 0;
59 nRoom = 0;
60 for(i=1; i<=(row<<1); i+=2)
61 for(j=1; j<=(column<<1); j+=2)
62 if(room[i][j] == '0')
63 {
64 nRoom++;
65 len = 0;
66 dfs(i, j);
67 if(len > max) max = len;
68 }
69
70 printf("%d
%d
", nRoom, max);
71 }
72 return 0;
73 }転載:
1 //POJ1164
2 //DFS standard , pay attention to the way to indicate the walls,
3 // ， “ “ ， 。
4 #include<iostream>
5 #include<cstdio>
6 #include<string>
7 #include<cstdlib>
8 #include<cstring>
9 #define N 60
10 using namespace std;
11 bool map[N][N];
12 int castle[N][N];
13 int room=0;//
14 int step,p,q;//step ，
15 bool inmap(int x,int y){//judge if the point is in the map
16 return ( x<=p && y<=q && x>0 && y>0 );
17 }
18 void search(int x,int y){//search from (x,y)
19 step++;
20 map[x][y] = true;
21
22 int temp = castle[x][y];
23 if (temp < 8){//do not have the south wall
24 if( inmap(x+1,y) && !map[x+1][y] )
25 search(x+1,y);
26 }
27 else temp -= 8;
28
29 if (temp < 4){//do not have the east wall
30 if( inmap(x,y+1) && !map[x][y+1] )
31 search(x,y+1);
32 }
33 else temp -= 4;
34
35 if (temp < 2){//do not have the north wall
36 if( inmap(x-1,y) && !map[x-1][y] )
37 search(x-1,y);
38 }
39 else temp -= 2;
40
41 if (temp < 1){//do not have the west wall
42 if( inmap(x,y-1) && !map[x][y-1] )
43 search(x,y-1);
44 }
45 }
46 int main(){
47 cin >> p >> q;
48 //input
49 for(int i=1;i<=p;i++)
50 for(int j=1;j<=q;j++)
51 cin >> castle[i][j];
52 //init
53 memset(map,false,sizeof(map));
54 //search
55 int lar = 0;
56 for(int i=1;i<=p;i++)
57 for(int j=1;j<=q;j++){
58 if( !map[i][j] ){
59 step = 0;
60 search(i,j);
61 room++;
62 if(lar < step )//find the largest room
63 lar = step;
64 }
65 }
66 //output
67 cout << room <<endl;
68 cout << lar << endl;
69 return 0;
70 }