Page 1 of 1

### 12291 - Polyomino Composer

Posted: Sun Aug 24, 2014 1:56 am
Why WA?

Code: Select all

``````#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){

while(1){
int N, n;
scanf("%d %d", &N, &n);
if(!n && !N){
return 0;
}
int numLarge = 0;
int markedLarge = 0;

char Grid[N][N];
char grid[n][n];
vector< vector<int> > arr(N, vector<int>(N, 0));

for(int i = 0; i<N; i++){
for(int j = 0; j<N; j++){
scanf(" %c", &Grid[i][j]);
if(Grid[i][j] == '*'){
numLarge++;
}
}
}
for(int i = 0; i<n; i++){
for(int j = 0; j<n; j++){
scanf(" %c", &grid[i][j]);
}
}

// Try each point of Grid
for(int I = 0; I<N; I++){
for(int J = 0; J<N; J++){
// Fit small polymino

if(arr[I][J]){
continue;
}

bool fits = true;
for(int i = 0; i<n && fits; i++){
for(int j = 0; j<n && fits; j++){
if(grid[i][j] == '*'){
if(I+i < 0 || I+i>=N || J+j<0 || J+j>=N){
fits = false;
continue;
}
if(arr[I+i][J+j]){
fits = false;
continue;
}
if(Grid[I+i][J+j]!='*'){
fits = false;
}
}
}
}

// If it fits, save changes to arr: do above loop but mark arr
// Update markedLarge too
if(fits){
for(int i = 0; i<n; i++){
for(int j = 0; j<n; j++){
if(grid[i][j] == '*'){
arr[I+i][J+j] = 1;
markedLarge++;
}
}
}
}

}
}

// Compare large polymino to arr: each block must be 1 on arr
// Or actually just count

/*for(int i = 0; i<N; i++){
for(int j = 0; j<N; j++){
printf("%d ", arr[i][j]);
}
printf("\n");
}*/

if(numLarge == markedLarge){
printf("1\n");
} else {
printf("0\n");
}

}

return 0;
}
``````

### Re: 12291 - Polyomino Composer

Posted: Sat Aug 30, 2014 12:14 am
Input:

Code: Select all

``````2 2
**
**
.*
.*
0 0
``````
AC output 1

### Re: 12291 - Polyomino Composer

Posted: Tue Dec 09, 2014 1:45 am
It looks like the judge's input has Polyominos that don't have the correct number of characters. In my AC code I pad the right size of the Polyomino with '.' if the line is too short.

### Re: 12291 - Polyomino Composer

Posted: Fri Jan 09, 2015 9:32 am
brianfry713 wrote:It looks like the judge's input has Polyominos that don't have the correct number of characters. In my AC code I pad the right size of the Polyomino with '.' if the line is too short.

### Re: 12291 - Polyomino Composer

Posted: Fri Jan 09, 2015 9:57 am

Code: Select all

``````#include<iostream>
#include<sstream>
#include<string>
#include<algorithm>
#include<iomanip>
#include<array>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<forward_list>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<utility>
#include<cctype>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<climits>
#include<cstdint>
#include<ciso646>
#include<cassert>

#define sc(x) scanf("%d",&x)
#define sc2(x,y) scanf("%d%d",&x,&y)
#define sc3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define sc4(w,x,y,z) scanf("%d%d%d%d",&w,&x,&y,&z)
#define scl(x) scanf("%lld",&x)
#define scl2(x,y) scanf("%lld%lld",&x,&y)
#define scl3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z)
#define scl4(w,x,y,z) scanf("%lld%lld%lld%lld",&w,&x,&y,&z)
#define pr(x) printf("%d",x)
#define pr2(x,y) printf("%d %d",x,y)
#define pr3(x,y,z) printf("%d %d %d",x,y,z)
#define pr4(w,x,y,z) printf("%d %d %d %d",w,x,y,z)
#define prl(x) printf("%lld",x)
#define prl2(x,y) printf("%lld %lld",x,y)
#define prl3(x,y,z) printf("%lld %lld %lld",x,y,z)
#define prl4(w,x,y,z) printf("%lld %lld %lld %lld",w,x,y,z)
#define prn(x) printf("%d\n",x)
#define prn2(x,y) printf("%d %d\n",x,y)
#define prn3(x,y,z) printf("%d %d %d\n",x,y,z)
#define prn4(w,x,y,z) printf("%d %d %d %d\n",w,x,y,z)
#define prln(x) printf("%lld\n",x)
#define prln2(x,y) printf("%lld %lld\n",x,y)
#define prln3(x,y,z) printf("%lld %lld %lld\n",x,y,z)
#define prln4(w,x,y,z) printf("%lld %lld %lld %lld\n",w,x,y,z)
#define memc(x,y) memcpy(&x,&y,sizeof(x))
#define mems(x,y) memset(x,y,sizeof(x))
#define ce(x,y) strcmp(x,y)
#define fli() freopen("in.txt","r",stdin)
#define flo() freopen("out.txt","w",stdout)
#define Rep(i,x,v) for(int i=x;i<v;i++)
#define Repe(i,x,v) Rep(i,x,v+1)
#define rep(i,v) Rep(i,0,v)
#define repe(i,v) rep(i,v+1)
#define Repr(i,x,v) for(int i=x;v<i;i--)
#define Repre(i,x,v) Repr(i,x,v-1)
#define repr(i,x) Repr(i,x,0)
#define repre(i,x) Repr(i,x,-1)
#define repv(i,x) for(auto i=x.begin();i!=x.end();i++)
#define reprv(i,x) for(auto i=x.rbegin();i!=x.rend();i++)
#define Repn(i,x,v) for(int i=x;i<v;i++,putchar('\n'))
#define repn(i,v) for(int i=0;i<v;i++,putchar('\n'))
#define bl putchar('\n')
#define gcc getchar()
#define pcc putchar
#define sz() size()
#define fi first
#define se second
#define pf push_front
#define pof pop_front
#define pb push_back
#define pob pop_back
#define mk make_pair
#define LL long long
#define MAX 1
using namespace std;

int main()
{
//fli();
int a,b,tm;
//char lo[102][102],sh[102][102],sam[102][102];
bool flag,temp;
while(sc2(a,b),a or b)
{
char lo[a][a+1],sh[b][b+1],sam[b][b+1];
rep(i,a)
scanf("%s",lo[i]);
rep(i,b)
scanf("%s",sh[i]);
rep(i,b)
{
temp=false;
rep(j,b)
{
if(sh[j][i]=='*')
{
tm=i;
temp=true;
break;
}
}
if(temp)
break;
}
if(tm!=0)
{
rep(i,b)
fill(sam[i],sam[i]+sizeof(sam[i]),'.');
for(int i=0,k=0;i<b;i++,k++)
{
for(int j=tm,l=0;j<b;j++,l++)
sam[k][l]=sh[i][j];
sam[k][b]='\n';
}
memc(sh,sam);
}
rep(i,b)
{
temp=false;
rep(j,b)
{
if(sh[j][i]=='*')
{
tm=j;
temp=true;
break;
}
}
if(temp)
break;
}
if(tm!=0)
{
rep(i,b)
fill(sam[i],sam[i]+sizeof(sam[i]),'.');
for(int i=tm,k=0;i<b;i++,k++)
{
for(int j=0,l=0;j<b;j++,l++)
sam[k][l]=sh[i][j];
sam[k][b]='\n';
}
memc(sh,sam);
}
rep(i,a)
{
rep(j,a)
{
flag=true;
rep(k,b)
{
rep(l,b)
{
if(sh[k][l]=='*')
{
if(lo[i+k][j+l]!='*')
flag=false;
}
}
}
if(flag)
{
rep(k,b)
rep(l,b)
if(sh[k][l]=='*')
{
if(lo[i+k][j+l]=='*')
lo[i+k][j+l]='.';
}
break;
}
}
if(flag)
break;
}
if(flag==false)
{
puts("0");
continue;
}
rep(i,a)
{
rep(j,a)
{
flag=true;
rep(k,b)
{
rep(l,b)
{
if(sh[k][l]=='*')
{
if(lo[i+k][j+l]!='*')
flag=false;
}
}
}
if(flag)
{
rep(k,b)
rep(l,b)
if(sh[k][l]=='*')
{
if(lo[i+k][j+l]=='*')
lo[i+k][j+l]='.';
}
break;
}
}
if(flag)
break;
}
if(flag==false)
{
puts("0");
continue;
}
rep(i,a)
{
rep(j,a)
if(lo[i][j]=='*')
{
flag=false;
break;
}
if(flag==false)
break;
}
if(flag==false)
{
puts("0");
continue;
}
else
puts("1");
continue;
}
return 0;
}``````

### Re: 12291 - Polyomino Composer

Posted: Fri Jan 09, 2015 10:33 pm
BlackBeard wrote:
brianfry713 wrote:It looks like the judge's input has Polyominos that don't have the correct number of characters. In my AC code I pad the right size of the Polyomino with '.' if the line is too short.

Code: Select all

``````4 3
.**
****
.**
.
**
.**
.
0 0``````
AC output 1

### Re: 12291 - Polyomino Composer

Posted: Fri Jan 09, 2015 10:40 pm
Let me know how your algorithm differs from mine.

As I read in the Polyominos if the length of a line is less than m or n I pad it with '.'
I also count the number of '*' in each and print 0 if the large doesn't have twice as many as the small.
I then shift both the large and small up and to the left as much as possible, and keep track of the new minimum height and width.
I then test every possible position for the small to fit into the large, if I get a match - then I mark those positions and again test every possible position for a match.

### Re: 12291 - Polyomino Composer

Posted: Fri Jan 09, 2015 10:58 pm
My algo:
1. first I shifted the small grid as left and as upper as possible(I didn't think I should do so for the larger grid as well)
2. then I traversed the large grid for any occurrence of the small grid. if found, filled that section of the larger grid with '.'. if none found then printed 0,
3. then I traversed again in the large grid for another occurrence and if found, I did the same. if none found then printed 0.
4. then I traversed the whole large grid and if I found any occurrence of '*' I printed 0. because if the two small piece made the larger piece the there would be no '*' in the larger grid after step 3.(if no '*' found then I printed 1)

by the way I didn't had to put '.' in the grids if there wasn't enough characters. I program gave right outputs for those kind of inputs

### Re: 12291 - Polyomino Composer

Posted: Tue Jan 13, 2015 1:41 am
Make sure you aren't reading and writing outside of array boundaries.

### Re: 12291 - Polyomino Composer

Posted: Mon May 02, 2016 10:25 pm
I can't seem to figure out what is wrong with the following code. Just to make the effort of reading the code a bit easy, I'll summarize my idea -
Idea
1) Trace the small image, and make list (ArrayList) which stores the information of the image.
2) Use the information of the trace(Arraylist) obtained to find the image in the big-image.
3) The code handles the scenario wherein the small image can be more than twice.
4) The code handles the scenario wherein you have to pad "*" (asterisk) if not present in the test-case.

Code: Select all

``````import java.io.BufferedReader;
import java.io.IOException;
import java.util.ArrayList;

class Main
{
private ArrayList<Point> trace;
private boolean parent[][];
private boolean child[][];
private String line;
private String tokens[];

public static void main(String ar[]) throws IOException
{
Main demo = new Main();
demo.solve();
}

public void solve() throws IOException
{
while (true)
{
trace = new ArrayList<Point>();
int parentRow = Integer.parseInt(tokens[0]);
int childRow = Integer.parseInt(tokens[1]);

if (parentRow == childRow && parentRow == 0)
{
return;
}

parent = new boolean[parentRow][parentRow];
child = new boolean[childRow][childRow];

for (int i = 0; i < parent.length; i++)
{
for (int j = 0; j < line.length(); j++)
{
parent[i][j] = line.charAt(j) == '*';
}
}

for (int i = 0; i < child.length; i++)
{
for (int j = 0; j < line.length(); j++)
{
child[i][j] = line.charAt(j) == '*';
}
}

Point startSmall = getStartPosition(child);
for (int i = 0; i < child.length; i++)
{
for (int j = 0; j < child.length; j++)
{
if (child[i][j])
{
Point temp = new Point(i, j);
child[temp.x][temp.y] = false;
}
}
}

boolean result = traceParent();
if (!result || getStartPosition(parent) != null)
{
System.out.println("0");
} else
{
System.out.println("1");
}
}
}

public boolean traceParent()
{
for (int i = 0; i < parent.length; i++)
{
for (int j = 0; j < parent.length; j++)
{
if (parent[i][j])
{
for (int k = 0; k < trace.size(); k++)
{
Point temp = trace.get(i);
int x = temp.x + i;
int y = temp.y + j;
if (!(x >= 0 && y >= 0 && x < parent.length && y < parent.length) || !parent[x][y])
{
return false;
}
parent[x][y] = false;
}
}
}
}
return true;
}

public Point getStartPosition(boolean image[][])
{
for (int i = 0; i < image.length; i++)
{
for (int j = 0; j < image.length; j++)
{
if (image[i][j])
{
return new Point(i, j);
}
}
}
return null;
}
}

class Point implements Comparable<Point>
{
int x;
int y;

public Point(int x, int y)
{
this.x = x;
this.y = y;
}

public int compareTo(Point that)
{
int xDiff = this.x - that.x;
if (xDiff == 0)
{
return this.y - that.y;
}
return xDiff;
}

public Point subtract(Point that)
{
return new Point(this.x - that.x, this.y - that.y);
}