//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();
}
Pour intégrer ce projet à votre site web, copiez le code suivant et collez-le dans le HTML de votre site web :