12291 - Polyomino Composer

All about problems in Volume 122. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

12291 - Polyomino Composer

Post by jddantes » 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;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12291 - Polyomino Composer

Post by brianfry713 » Sat Aug 30, 2014 12:14 am

Input:

Code: Select all

2 2
**
**
.*
.*
0 0
AC output 1
Check input and AC output for thousands of problems on uDebug!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12291 - Polyomino Composer

Post by brianfry713 » 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.
Check input and AC output for thousands of problems on uDebug!

BlackBeard
New poster
Posts: 18
Joined: Wed Dec 17, 2014 9:44 pm

Re: 12291 - Polyomino Composer

Post by BlackBeard » 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.
Can you explain please...?

BlackBeard
New poster
Posts: 18
Joined: Wed Dec 17, 2014 9:44 pm

Re: 12291 - Polyomino Composer

Post by BlackBeard » Fri Jan 09, 2015 9:57 am

Also I don't know why I'm getting wa. please help...

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;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12291 - Polyomino Composer

Post by brianfry713 » 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.
Can you explain please...?

Code: Select all

4 3
.**
****
.**
.
**
.**
.
0 0
AC output 1
Check input and AC output for thousands of problems on uDebug!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12291 - Polyomino Composer

Post by brianfry713 » 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.
Check input and AC output for thousands of problems on uDebug!

BlackBeard
New poster
Posts: 18
Joined: Wed Dec 17, 2014 9:44 pm

Re: 12291 - Polyomino Composer

Post by BlackBeard » 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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12291 - Polyomino Composer

Post by brianfry713 » Tue Jan 13, 2015 1:41 am

Make sure you aren't reading and writing outside of array boundaries.
Check input and AC output for thousands of problems on uDebug!

zodiacLeo
New poster
Posts: 2
Joined: Sun Feb 07, 2016 8:01 pm

Re: 12291 - Polyomino Composer

Post by zodiacLeo » 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.io.InputStreamReader;
import java.util.ArrayList;

class Main
{
    private ArrayList<Point> trace;
    private boolean parent[][];
    private boolean child[][];
    private String line;
    private String tokens[];
    private BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    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>();
            tokens = br.readLine().trim().split("[ ]+");
            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++)
            {
                line = br.readLine().trim();
                for (int j = 0; j < line.length(); j++)
                {
                    parent[i][j] = line.charAt(j) == '*';
                }
            }

            for (int i = 0; i < child.length; i++)
            {
                line = br.readLine().trim();
                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);
                        trace.add(temp.subtract(startSmall));
                        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);
    }

    public Point add(Point that)
    {
        return new Point(this.x + that.x, this.y + that.y);
    }

    public String toString()
    {
        return "Point x = " + this.x + ",  y = " + this.y;
    }
}

Post Reply

Return to “Volume 122 (12200-12299)”