//BAEKJOON 6870_네모네모로직 구현?
//TLE... 포기할게요ㅠ
#include <stdio.h>
#include <stdlib.h>
#include <vector>
using namespace std;

int n, m;
vector<int> row[35], col[35];
vector<vector<char>> rowPatterns[35];

struct nemonemologic {
 private:
    char **Nono;
    int rownum=0, colnum=0;
 public:
    void Init(int, int);
    void Destroy();
    void Print();
    void GetRow(int r, int idx, int pos, vector<char> &line, vector<vector<char>> &rowP); // 행 패턴 생성
    bool CheckCol(int, bool);
    bool Solve(int);
};

void nemonemologic::Init(int r, int c) {
    Nono=(char **)malloc(sizeof(char *)*(r+2));
    for(int j=0; j<r+2; j++) {
        Nono[j]=(char *)malloc(sizeof(char)*(c+2));
    }

    if(Nono) {
        for(int i=0; i<r+2; i++) {
            for(int j=0; j<c+2; j++)
                Nono[i][j]='\0';
        }
        rownum=r, colnum=c;
    }
        
}
void nemonemologic::Destroy() {
    for(int j=0; j<rownum+2; j++) {
        free(Nono[j]);
    }
    free(Nono);
}
// 행 패턴
void nemonemologic::GetRow(int r, int idx, int pos, vector<char> &line, vector<vector<char>> &rowP) {
    if(idx==row[r].size()) { //다 채움
        for(int i=pos; i<=colnum; i++) line[i]='.';
        rowP.push_back(line);
        return;
    }

    int b=row[r][idx];
    for(int s=pos; s+b-1<=colnum; s++) {
        for(int i=pos; i<s; i++) line[i]='.';
        for(int i=s; i<s+b; i++) line[i]='*';

        int npos=s+b;
        if(npos <=colnum) line[npos]='.';

        GetRow(r, idx+1, npos+1, line, rowP);
    }
}
// 열 확인
bool nemonemologic::CheckCol(int c, bool final) {
    int cnt=0;
    int color[35], ccnt=0;//색칠 수

    int sum=0, first=-1; //빈 칸 개수, 남은 블럭 개수 비교 위한
    
    for(int i=1; i<=rownum; i++) {
        if(Nono[i][c]=='\0') {
            first=i;
            break;
        }
        else if(Nono[i][c]=='*') cnt++;
        else {
            if(cnt>0) color[ccnt++]=cnt;
            cnt=0;
        }
    }
    if(cnt) color[ccnt++]=cnt;

    if(final) { //최종
        if(ccnt!=col[c].size()) return false;
        for(int i=0; i<ccnt; i++) {
            if(color[i]!=col[c][i]) return false;
        }
        return true;
    }

    // 최종X

    if(ccnt>col[c].size()) return false; // 과도한 블럭
    
    for(int i=0; i<ccnt; i++) {
        if(color[i]>col[c][i]) return false; // 블럭 길이 긺
    }

    if(first!=-1) { // 중간에 블럭이 끊긴 경우 : 남은 칸, 필요한 블럭 개수 비교 필요
        int remainSpace=rownum-first+1; 
        int needSpace=0; //남은 블럭+공간

        for(int i=ccnt; i<col[c].size(); i++) {
            needSpace+=col[c][i];
            if(i>ccnt) needSpace++;
        }
        if(needSpace > remainSpace) return false;
    }
    return true;
}
// 풀이
bool nemonemologic::Solve(int r) {
    if(r==rownum+1) return true; //solve
    
    for(int p=0; p<rowPatterns[r].size(); p++) {
        for(int j=1; j<=colnum; j++) Nono[r][j]=rowPatterns[r][p][j];

        bool next=true; //다음 행?
        for(int j=1; j<=colnum; j++) {
            if(CheckCol(j, (r==rownum ? true:false))==false) {
                next=false;
                break;
            }
        }

        if(next && Solve(r+1)) return true;
    }

    for(int i=1; i<=colnum; i++) Nono[r][i]='\0'; //reset
    return false;
}

void nemonemologic::Print() {
    for(int i=1; i<=rownum; i++) {
        for(int j=1; j<=colnum; j++) {
            printf("%c", Nono[i][j]);
        }
        puts("");
    }
}

int main() {
    scanf("%d %d", &n, &m);
    nemonemologic Nonogram;
    Nonogram.Init(n, m);

    for(int i=1; i<=n; i++) {
        while(1) {
            int a;
            scanf("%d", &a);
            if(!a) break;

            row[i].push_back(a);
        }
    }
    
    for(int i=1; i<=m; i++) {
        while(1) {
            int a;
            scanf("%d", &a);
            if(!a) break;

            col[i].push_back(a);
        }
    }

    for(int r=1; r<=n; r++) { // 모든 행 패턴 제작
        vector<char> line(m+2, '\0'); 
        Nonogram.GetRow(r, 0, 1, line, rowPatterns[r]); //(행 번호, row[r][인덱스], ..)
    }

    if(Nonogram.Solve(1))
        Nonogram.Print();
    Nonogram.Destroy();
}

Intégrer sur un site web

Pour intégrer ce projet à votre site web, copiez le code suivant et collez-le dans le HTML de votre site web :