캐슬 문제(단순 DFS)

2815: 성 문제 보기 제출 통계 알림 질문 총 시간 제한: 1000ms 메모리 제한: 65536kB 설명 성 전체 몇 개의 방, 가장 큰 방이 얼마나 큰지 계산하는 프로그램을 작성하세요.성은 mn(m≤50, n≤50)개의 네모로 분할되어 각 네모마다 0~4면의 벽이 있을 수 있다.입력 프로그램이 표준 입력 장치에서 데이터를 읽습니다.첫 번째 줄은 두 개의 정수로 각각 남북방향, 동서방향의 네모난 수이다.다음 입력 줄에서 각 블록은 하나의 숫자(0≤p≤50)로 설명한다.네모난 블록 주위의 벽을 한 숫자로 표시하고, 1은 서쪽 벽, 2는 북쪽 벽, 4는 동쪽 벽, 8은 남쪽 벽을 나타낸다.각 블록은 주변 벽을 나타내는 숫자의 합으로 표시됩니다.성곽의 내벽은 두 번 계산되고 네모난 벽(1,1)의 남쪽 벽은 네모난 벽(2,1)의 북쪽 벽이기도 하다.입력한 데이터는 성에 적어도 두 개의 방이 있다는 것을 보장한다.성곽의 방수, 성곽의 최대 방에 포함된 네모난 수를 출력합니다.결과는 표준 출력 장치에 표시됩니다.샘플 입력 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 출처 1164
문제풀이: dfs 연결 블록 문제를 구합니다.방문하지 않은 점에서 출발하여 dfs 이 점 부근에 도착할 수 있는 모든 점, 함수 반환값은 이 점 주위에 방문하지 않았고 도착할 수 있는 모든 점의 수를 합한 것이다.각 반환치의 크기를 비교하면 가장 큰 것은 제목이 요구하는 가장 큰 방의 네모난 숫자이다.만약에 하나의 연결 블록을 구한 후에 모든 방을 덮지 않았다면, 여전히 방이vis가 0이면 다시 연결 블록을 구하고 최대 방의 네모난 블록을 비교한다.다시 블록을 구할 때마다num++를 사용하면 모두 몇 개의 방이 있는지 계산할 수 있다.
생각: 1. & 좋은 기호 2. 다음 단계가 갈 수 있는지 없는지를 판단하고 가야 한다. 3. 줄과 열을 분명히 한 다음에 아래로 써야 한다.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
const int maxn = 55;
int room[maxn][maxn], vis[maxn][maxn], maxsiz, num;
int m, n;

int dfs(int x, int y)
{
    vis[x][y] = num;
    int siz1 = 0;
    if (x - 1 >= 1 && !vis[x - 1][y] && (room[x][y] & 2) == 0) {
        siz1 += dfs (x - 1, y);

    }
    if (x + 1 <= m && !vis[x + 1][y] && (room[x][y] & 8) == 0) {
        siz1 += dfs (x + 1, y);
    }
    if (y + 1 <= n && !vis[x][y + 1] && (room[x][y] & 4) == 0) {
        siz1 += dfs (x, y + 1);
    }
    if (y - 1 >= 1 && !vis[x][y - 1] && (room[x][y] & 1) == 0) {
        siz1 += dfs (x, y - 1);
    }
    return siz1 + 1;
}

int main()
{
    #ifndef ONLINE_JUDGE
    freopen ("in.txt", "r", stdin);
    #endif // ONLINE_JUDGE
    scanf ("%d%d", &m, &n);
    memset (room, 0, sizeof(room));
    memset (vis, 0, sizeof(vis));
    maxsiz = 0;
    num = 0;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            scanf ("%d", &room[i][j]);
        }
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (!vis[i][j]) {
                num++;
                int siz = dfs (i, j);
                if (siz > maxsiz) {
                    maxsiz = siz;
                }
            }
        }
    }
    printf ("%d
%d
", num, maxsiz);
    return 0;
}