游客 注册 | 登录
中文 | En

2263 - The Castle

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

 Figure 1 shows the map of a castle. Write a program that calculates 

<span>1. how many rooms the castle has</span> 


<span>2. how big the largest room is</span> 


<span>The castle is divided into m * n (m&lt;=50, n&lt;=50) square modules. Each such module can have between zero and four walls.</span> 


<img alt="" src="http://tk.hustoj.com:80/attached/image/20131210/20131210184301_17138.png" />

  

<span style="font-family:Consolas;">#<span>&nbsp; </span>= Wall<span>&nbsp;&nbsp; </span></span>


<span style="font-family:Consolas;">|<span>&nbsp; </span>= No wall</span> 


<span style="font-family:Consolas;">-<span>&nbsp; </span>= No wall</span> 


&nbsp;

题目输入

Your program is to read from standard input. The first line contains the number of modules in the north-south direction and the second line contains 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

题目输出

 Your program is to write to standard output: First the number of rooms, then the area of the largest room (counted in modules).

输入/输出样例

输入格式

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

输出格式

5
9

C++解答

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 60, M = 100010;
int n, m, p;
int a[N][N][4];
bool b[N][N];
int q[M][3];
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
int maxx = -1, tot;
void bfs(int x, int y){
    memset(q, 0, sizeof q);
    tot ++;
    int tail = 1, head = 0, xx, yy;
    q[1][1] = x, q[1][2] = y;
    while (head < tail){
        head ++;
        for (int i = 0; i < 4; i ++){
            xx = q[head][1] + dx[i];
            yy = q[head][2] + dy[i];
            if (xx > 0 && xx <= n && yy > 0 && yy <= m && b[xx][yy] && a[q[head][1]][q[head][2]][i] == 0){
                tail ++;
                b[xx][yy] = false;
                q[tail][1] = xx;
                q[tail][2] = yy;
            }
        }
    }
    maxx = max(tail - 1, maxx);
}
int main(){
    memset(b, true, sizeof b);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++){
            scanf("%d", &p);
            if (p >= 8) {
                p -= 8;
                a[i][j][1] = 1;
            }
            if (p >= 4) {
                p -= 4;
                a[i][j][3] = 1;
            }
            if (p >= 2){
                p -= 2;
                a[i][j][0] = 1;
            }
            if (p >= 1) {
                p -= 1;
                a[i][j][2] = 1;
            }
        }
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            if (b[i][j]) bfs(i, j);
    printf("%d\n%d\n", tot, maxx);
    return 0;
}

Java解答

import java.util.Scanner;
public class Main{
    static int map[][],vis[][],n,m,count;
    public static void main(String[]args){
        Scanner in=new Scanner(System.in);
        while(in.hasNextInt()){
            int n=in.nextInt();
            int m=in.nextInt();
            map=new int[n][m];
            vis=new int[n][m];
            int i,j;
            for(i=0;i<n;i++)
                for(j=0;j<m;j++)
                    map[i][j]=in.nextInt();
            int maxroom=0,cnt=0;
            for(i=0;i<n;i++)
                for(j=0;j<m;j++){
                    count=0;
                    dfs(i,j);
                    if(count!=0)
                        cnt++;
                    if(maxroom<count)
                        maxroom=count;
                }
            System.out.println(cnt);
            System.out.println(maxroom);
        }
    }
    public static void dfs(int x,int y){
        if(vis[x][y]==1)
            return; //如果已经访问过，回到上一个位置
        else{
            count++;//否则，count加一统计该房间包含的方格数；并对该方格标记为已访问过。
            vis[x][y]=1;
        }
        if(map[x][y]<8)//判断是否有南墙，没有，则向下继续搜索
            dfs(x+1,y);
        else
            map[x][y]%=8;//有南墙，对8求余；向下判断。
        if(map[x][y]%8<4)//判断是否有东墙，没有，则向右继续搜索。
            dfs(x,y+1);
        else
            map[x][y]%=4;//有东墙，对4求余，继续向下判断。
        if(map[x][y]%4<2)//判断是否有北墙，没有，则向上继续搜索
            dfs(x-1,y);
        else
            map[x][y]%=2;//有北墙，对2求余，继续向下判断
        if(map[x][y]%2==0)//判读是否有西墙，没有，向左继续搜索
            dfs(x,y-1);
    }
}
请先登陆