성 문제 (DFS)

성 문제 (검색) 
총 시간 제한: 1000 ms 메모리 제한: 65536 kB
묘사 하 다.  (그림 1)
# = Wall  | = No wall  - = No wall
그림 1 은 성의 지형도 이다.성 이 모두 몇 개의 방 이 있 는 지, 가장 큰 방 이 얼마나 큰 지 계산 하 는 프로그램 을 만들어 보 세 요.성 은 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
예: 11 의 이 진 은 1011 이 고 각 이 진 은 각각 '남 벽', '동 벽', '북 벽', '서 벽' 을 나타 내 며 1 은 벽 이 있 음 을 나타 내 고 0 은 벽 이 없다 는 것 을 나타 낸다.비트 와 연산 자 & 의 사용: 예 를 들 어 11 & 4 < = > 1011 & 0100 = 0000 = 0.같은 것 은 1 이 고, 다른 것 은 0 이다.세로: 1011        &0100            -----            0000
문제 풀이 방향: 각 사각형, 깊이 우선 검색 (DFS) 을 통 해 이 사각형 이 도달 할 수 있 는 모든 위치 에 염색 합 니 다.마지막 으로 총 몇 가지 색깔 과 각 색깔 의 수량 을 통계 해 냈 다.예 를 들 어 1, 2, 3, 3, 1, 1, 2, 3, 4, 1, 1, 5, 3, 1, 5, 5, 5, 5, 5, 5, 5, 5, 3. 모두 5 개의 방 이 있 고 가장 큰 방 (1) 은 9 개의 칸 을 차지한다.
[해법 1: 귀속]
[해법 2: 스 택]
/ * 이것 은 BFS 템 플 릿 을 모방 한 표기 법 입 니 다. O (∩ ∩) O 하하 ~, 이제 야 BFS 와 DFS (스 택 해법) 의 차 이 를 알 게 되 었 습 니 다. 사실 BFS 템 플 릿 을 사용 하면 DFS 를 실현 할 수 있 습 니 다. 스 택 으로 쓴 DFS 와 대열 로 쓴 BFS 는 조금 다 릅 니 다. 그것 이 바로 그들 이 사용 하 는 데이터 구조 가 다 릅 니 다.이 두 가지 서로 다른 데이터 구조의 서로 다른 특성 때문에 심층 검색 과 광 검색 효과 가 다 릅 니 다. * * * * * * *스 택 은 후진 이 먼저 나 옵 니 다. 그래서 매번 에 처음으로 광 수 와 같이 읽 을 수 있 는 첫 번 째 단계 에서 갈 수 있 는 노드 를 찾 습 니 다. 그 다음 에 스 택 요 소 를 기점 으로 이 점 에서 한 걸음 에 도착 할 수 있 는 노드 를 아래로 찾 습 니 다. 그러나 매번 에 조회 하 는 요 소 는 모두 이번에 옮 겨 다 니 는 마지막 요소 입 니 다. 즉, 두 번 째 조 회 는 모두 출발점 에서 도착 할 수 있 는 다음 요소 입 니 다. * * * * * * * * * * * * * * * * * *대기 열 은 먼저 나 가 고 매번 에 처음으로 읽 을 수 있 는 첫 번 째 단계 가 걸 을 수 있 는 노드 입 니 다. 그 다음 에 팀 의 첫 번 째 요 소 를 기점 으로 이 점 에서 한 걸음 에 도착 할 수 있 는 노드 를 찾 습 니 다. 그러나 매번 조회 할 때 한 요 소 를 먼저 조회 합 니 다. 이 층 이 끝 날 때 까지 다음 층 을 찾 습 니 다. 윗 층 요 소 는 항상 먼저 들 어 갑 니 다 * /

//AC
#include
#include
#include
using namespace std;
int R,C;    //   
int rooms[60][60];
int color[60][60];  //          
int maxRoomArea=0,roomNum=0;
int roomArea;
//     ：
void Dfs(int i,int k)
{
    if (color[i][k])
        return ;
    ++roomArea;
    color[i][k]=roomNum;
    if ((rooms[i][k]&1)==0)	
        Dfs(i,k-1); 	//   
    if ((rooms[i][k]&2)==0)
        Dfs(i-1,k); 	//   
    if ((rooms[i][k]&4)==0)
        Dfs(i,k+1); 	//   
    if ((rooms[i][k]&8)==0)
        Dfs(i+1,k); 	//   
}
int main()
{
    cin>>R>>C;
    for (int i=1;i<=R;i++)
        for (int k=1;k<=C;k++)
            cin>>rooms[i][k];
    memset(color,0,sizeof(color));
    for (int i=1;i<=R;i++)
    {
        for (int k=1;k<=C;k++)
        {
            if (!color[i][k])
            {
                ++roomNum;
                roomArea=0;
                Dfs(i,k);
                maxRoomArea=max(roomArea,maxRoomArea);
            }
        }
    }
    cout<

[해법 3: 사실 이것 도 스 택 으로 해결 한 것 입 니 다. 안에 사 용 된 구조 체 내의 구조 함수 일 뿐 두 개의 구조 체 변수 가 아 닙 니 다.]

//AC
#include
#include
#include
using namespace std;

int mark[60][60];
int room[60][60];
int n,m,num=0,area,maxarea;
struct data
{
    int x,y;
};

void dfs(int x,int y)
{
    stack stk;
    data p,pp;
    p.x=x;
    p.y=y;
    stk.push(p);
    while (!stk.empty())
    {
        p=stk.top();
        if (mark[p.x][p.y])
            stk.pop();
        else
        {
            ++area;
            mark[p.x][p.y]=1;
            if ((room[p.x][p.y]&1)==0&&p.y>0&&!mark[p.x][p.y-1])
            {
                pp.x=p.x;
                pp.y=p.y-1;
                stk.push(pp);
            }
            if ((room[p.x][p.y]&2)==0&&p.x>0&&!mark[p.x-1][p.y])
            {
                pp.x=p.x-1;
                pp.y=p.y;
                stk.push(pp);
            }
            if ((room[p.x][p.y]&4)==0&&p.y+1maxarea)
                        maxarea=area;
                }
            }
        }
        printf("%d
%d
",num,maxarea);
    }
    return 0;
}