글 읽기 - 5%에서 멈추네요.. 흠 어느 부분이 빈틈인지 모르겠습니다.

rladnjsrb9999 2년 전 0

문제 찾아주실분.......

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>

using namespace std;

int N;
string graph[7][7];
string temp_graph[7][7];
int student_count=0;
int result=0;

void dfs(int idx1, int idx2, int direction)
{
    if(idx1!=1 && (direction==0 || direction==1) && temp_graph[idx1-1][idx2]!="O")
    {
        temp_graph[idx1-1][idx2]="T";
        dfs(idx1-1,idx2,1);
    }
    if(idx1!=N && (direction==0 || direction==2) && temp_graph[idx1+1][idx2]!="O")
    {
        temp_graph[idx1+1][idx2]="T";
        dfs(idx1+1,idx2,2);
    }
    if(idx2!=1 && (direction==0 || direction==3) && temp_graph[idx1][idx2-1]!="O")
    {
        temp_graph[idx1][idx2-1]="T";
        dfs(idx1,idx2-1,3);
    }
    if(idx2!=N && (direction==0 || direction==4) && temp_graph[idx1][idx2+1]!="O")
    {
        temp_graph[idx1][idx2+1]="T";
        dfs(idx1,idx2+1,4);
    }
}

void bf(int count)
{
    if(count==3)
    {
        for(int i=1; i<=N; i++)
        {
            for(int j=1; j<=N; j++)
                temp_graph[i][j]=graph[i][j];
        }
        
        for(int i=1; i<=N; i++)
        {
            for(int j=1; j<=N; j++)
            {
                if(graph[i][j]=="T")
                    dfs(i,j,0);
            }
        }
        int temp_count=0;
        for(int i=1; i<=N; i++)
        {
            for(int j=1; j<=N; j++)
            {
                if(temp_graph[i][j]=="S")
                    temp_count++;
            }
        }
        if(temp_count==student_count)
            result=1;
        return;
    }
    
    for(int i=1; i<=N; i++)
    {
        for(int j=1; j<=N; j++)
        {
            if(graph[i][j]=="X")
            {
                graph[i][j]="O";
                bf(count+1);
                graph[i][j]="X";
            }
        }
    }
}

int main()
{
    // 문자열 있을 때는 index=0 부터
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    scanf("%d", &N);
    for(int i=1; i<=N; i++)
    {
        for(int j=1; j<=N; j++)
        {
            cin >> graph[i][j];
            if(graph[i][j]=="S")
                student_count++;
        }
    }
    
    bf(0);
    
    if(result==1)
        printf("YES");
    else
        printf("NO");
    
    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

5%에서 멈추네요.. 흠 어느 부분이 빈틈인지 모르겠습니다.

rladnjsrb9999 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말