The Castle
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 8317 Accepted: 4693
Description
poj1741,1 2 3 4 5 6 7
#############################
1 # | # | # | | #
#####—#####—#---#####—#
2 # # | # # # # #
#—#####—#####—#####—#
3 # | | # # # # #
#—#########—#####—#---#
4 # # | | | | # #
#############################
(Figure 1)
# = Wall
| = No wall
- = No wall
Figure 1 shows the map of a castle.Write a program that calculates
Input
Your program is to read from standard input. The first line contains the number of modules in the north-south direction and the number of modules in the east-west direction. In the following lines each module is described by a number (0 <= p <= 15). This number is the sum of: 1 (= wall to the west), 2 (= wall to the north), 4 (= wall to the east), 8 (= wall to the south). Inner walls are defined twice; a wall to the south in module 1,1 is also indicated as a wall to the north in module 2,1. The castle always has at least two rooms.
Output
Your program is to write to standard output: First the number of rooms, then the area of the largest room (counted in modules).
Sample Input
4
7
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
Source
IOI 1994
問題鏈接:POJ1164 The Castle
問題簡述:(略)
問題分析:
????這是一個搜索問題,用DFS實現。
程序說明:(略)
參考鏈接:(略)
題記:(略)
AC的C語言程序如下:
/* POJ1164 The Castle */#include <stdio.h>int drow[] = {0, -1, 0, 1};
int dcol[] = {-1, 0, 1, 0};#define N 50
int maze[N][N], n, m, sum, cnt;void dfs(int row, int col)
{int s = maze[row][col], i;sum++;maze[row][col] = -1;for(i = 0; i < 4; i++) {if(s % 2 == 0) {int nrow = row + drow[i];int ncol = col + dcol[i];if(nrow >= 0 && nrow < n && ncol >= 0 && ncol < m && maze[nrow][ncol] != -1)dfs(nrow, ncol);}s /= 2;}
}int main(void)
{int maxsum, i, j;while(scanf("%d%d", &n, &m) != EOF) {for(i = 0; i < n; i++)for(j = 0; j < m; j++)scanf("%d", &maze[i][j]);cnt = maxsum = 0;for(i = 0; i < n; i++)for(j = 0; j < m; j++)if(maze[i][j] != -1) {sum = 0;dfs(i, j);cnt++;if(sum > maxsum)maxsum = sum;}printf("%d\n%d\n", cnt, maxsum);}return 0;
}
版权声明:本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。
工作时间:8:00-18:00
客服电话
电子邮件
admin@qq.com
扫码二维码
获取最新动态