uva-387-暴力枚举

题意:

给你一些小方块,问是不是能组成一个4X4的大方块,所有方块全部要使用,裸枚举

#include <iostream>
#include <stdio.h>
#include <memory.h> using namespace std;
const int NN = ;
class Piece
{
private:
int r;
int c;
int** p;
public:
Piece()
: r(), c()
{
p = NULL;
}
Piece(int r, int c, int (*pp)[NN])
{
this->r = r;
this->c = c;
this->p = new int*[r]; for(int i = ; i < r; i++)
{
this->p[i] = new int[c];
memcpy(this->p[i], pp[i], c * sizeof(int));
}
}
~Piece()
{
for(int i = ; i < r; i++)
delete[] p[i];
delete this->p;
}
int getR()
{
return this->r;
}
int getC()
{
return this->c;
}
int ** getP()
{
return this->p;
} }; int N;
int r, c;
int m[][];
int vis[NN];
Piece* piece[NN];
int pi = ;
void dump()
{
for(int i = ; i < pi; i++)
for(int j = ; j < piece[i]->getR(); j++)
{
for(int k = ; k < piece[i]->getC(); k++)
cout << piece[i]->getP()[j][k];
cout << endl;
}
}
bool judge(int y, int x, Piece* p)
{
for(int i = ; i < p->getR(); i++)
for(int j = ; j < p->getC(); j++)
if(p->getP()[i][j] != && m[i + y][x + j] != )
{
return false;
}
return true;
}
void reset(int x, int y, int r, int c, int cur)
{
for(int i = ; i < r; i++)
for(int j = ; j < c; j++)
{
if(m[y + i][x + j] != cur)
continue;
m[y + i][x + j] = ;
}
} void copy(int x, int y, int r, int c, int** src)
{
for(int i = ; i < r; i++)
for(int j = ; j < c; j++)
{
if(m[y + i][x + j])
continue;
m[y + i][x + j] = src[i][j];
}
}
bool dfs(int cur)
{
if(cur == pi)
{
for(int i = ; i < ; i++)
{
for(int j = ; j < ; j++)
if(m[i][j] == )
return false;
}
return true;
}
//对当前的cur,枚举每一个坐标X,Y
for(int i = ; i < ; i++)
{
for(int j = ; j < ; j++)
{
if(m[i][j] && (piece[cur]->getP()[][]))
continue;
if(!judge(i, j, piece[cur]))
continue;
int r = piece[cur]->getR();
int c = piece[cur]->getC();
copy(j, i, r, c, piece[cur]->getP());
int ok = dfs(cur + );
if(ok)
return ok;
reset(j, i, r, c, cur + );
}
}
return false;
}
int main()
{
//freopen("d://1.text", "r", stdin);
int t = ;
while (cin >> N && N)
{
if(t != )
cout << endl;
++t;
memset(m, , sizeof(m));
memset(piece, , sizeof(piece));
memset(vis, , sizeof(vis));
int p[NN][NN];
pi = ;
for(int i = ; i <= N; i++)
{
scanf("%d %d", &r, &c);
for(int j = ; j < r; j++)
for(int k = ; k < c; k++)
{
char t;
cin >> t;
if(t == '')
p[j][k] = ;
else
p[j][k] = i;
}
Piece* pp = new Piece(r, c, p);
piece[pi++] = pp;
}
bool ok = dfs();
if(!ok)
{
cout << "No solution possible" << endl;
}
else
{
for(int i = ; i < ; i++)
{
for(int j = ; j < ; j++)
cout << m[i][j];
cout << endl;
}
}
}
// dump(); return ;
}
上一篇:20175312 2018-2019-2 《Java程序设计》第5周学习总结


下一篇:网络地址转换NAT应用实验