The goal of this problem is to write a program which will take from 1 to 5 puzzle pieces
such as those shown below and arrange them, if possible, to form a square.
The pieces cannot be rotated or flipped from their original orientation in an attempt to form
a square from the set. All of the pieces must be used to form the square. There may be more
than one possible solution for a set of pieces,
and not every arrangement will work even
with a set for which a solution can be found.
Input:
The input file for this program contains several puzzles (i.e. sets of puzzle pieces) to be solved. Thefirst line of the file is the number of pieces in the first puzzle. Each piece is then
specified by listing a single line with two integers, the number of rows and columns in the
piece, followed by one or more lines which specify the shape of the piece. Th
specification consists of `0' and `1' characters, with the `1' characters indicating the solid
shape of the puzzle (the `0' characters are merely placeholders). For example, piece `A'
above would be specified as follows
2 3
111
101
The pieces should be numbered by the order they are encountered in the puzzle. That is, the
first piece in a puzzle is piece #1, the next is piece #2, etc. All pieces may be assumed to be
valid and no larger than 4 rows by 4 columns.
The line following the final line of the last piece contains the number of pieces in the next
puzzle, again followed by the puzzle pieces and so on. The end of the input file is indicated
by a zero in place of the number of puzzle pieces.
Output
Your program should report a solution, if one is possible, in the format shown by the
examples below. A 4-row by 4-column square should be created, with each piece occupying
its location in the solution. The solid portions of piece #1 should be replaced with `1'
characters, of piece #2 with `2' characters, etc. The solutions for each puzzle should be
separated by a single blank line.
If there are multiple solutions, any of them is acceptable. For puzzles which have no
possible solution simply report ``No solution possible''.
Sample Input
4
2 3
111
101
4 2
01
01
11
01
2 1
1
1
3 2
10
10
11
4
1 4
1111
1 4
1111
1 4
1111
2 3
111
001
5
2 2
11
11
2 3
111
100
3 2
11
01
01
1 3
111
1 1
1
0
Sample Output
1112
1412
3422
3442
No solution possible
1133
1153
2223
2444
8  3481 
I have done this problem before! The point of a programming contest is to solve it on your own.
If you have an idea for implementation, but are having troubles implementing it, post your specific problems here. We're not just going to give you answers for a non-trivial problem with many methods of solving it.
This link includes pictures for people, if the original poster comes back. http://uva.onlinejudge.org/index.php...em&problem=323
I try but I need your help if You can
I want to see this program in C
Assumption: Input is not a problem for you.
1. Have you figured out what type of structure you're going to store the pieces in?
2. What type of algorithm do you intend on using?
- Break down your algorithm into parts.
i will use array
and I am not good in algorithm
how to break down algorithm into parts
Start with pseudocode. You are better off not writing any C code until you've worked out the algorithm.
I try to make the algorithm but it so difficult
how to make it
please any body know this program or algorithm answer me
I have exam very soon
... This question would be absurdly hard for an exam question, given that it is a programming contest question. Even for myself, it would probably take a half-day or more to solve, with computer available. I recommend you tackle a simpler problem to study for your exam. Since we do not know your course material, it's hard for us to suggest such a problem.
If you really want to pursue this further, really describe your structure.
What's in your array? What type of array is it?
How are you using the array? What does this array represent?
If you were to place 2 puzzle pieces, how would you determine if they intersect?
Sign in to post your reply or Sign up for a free account.
Similar topics
by: engsol |
last post by:
There is a number puzzle which appears in the daily paper.
Because I'm between Python projects, I thought it might be
fun to write a program to solve it....20 minute job, max.
On closer...
|
by: Protoman |
last post by:
Can you help me? For 4, my square root funct gives 4 instead of 2;
here's the code:
#include <iostream>
#include <cstdlib>
using namespace std;
template<class T>
T Abs(T Nbr)
{
|
by: xavier vazquez |
last post by:
I have a problem with a program that does not working properly...when the program run is suppose to generate a cross word puzzle , when the outcome show the letter of the words overlap one intop of...
|
by: xavier vazquez |
last post by:
have a problem with a program that does not working properly...when the program run is suppose to generate a cross word puzzle , when the outcome show the letter of the words overlap one intop of the...
|
by: ashish0799 |
last post by:
HI I M ASHISH I WANT ALGORYTHMUS OF THIS PROBLEM
Jigsaw puzzles. You would have solved many in your childhood and many people still
like it in their old ages also. Now what you have got to do...
|
by: oncue01 |
last post by:
Word Puzzle
Task
You are going to search M words in an N × N puzzle. The words may have
been placed in one of the four directions as from (i) left to right (E), (ii) right
to left (W), (iii) up...
|
by: Greatness |
last post by:
Ceramic Floor Tile
You’re working for a company that lays ceramic floor tile, and they need a program that estimates the number of boxes of tile for a job. A job is estimated by taking the...
|
by: ayiha |
last post by:
Problem statement:
You might have come across a puzzle which contains 15 numbered square pieces, which can be moved horizontally or vertically. A possible arrangement of these pieces is shown...
|
by: logickills.root |
last post by:
Post all your random and cool program ideas.
Perfect place for people to find inspiration.
Anything from beginner to complex.
Make it quite vague or provide some guidelines.
|
by: honey777 |
last post by:
Problem: 15 Puzzle
This is a common puzzle with a 4x4 playing space with 15 tiles, numbered 1 through 15. One "spot" is always left blank. Here is an example of the puzzle:
The goal is to...
|
by: taylorcarr |
last post by:
A Canon printer is a smart device known for being advanced, efficient, and reliable. It is designed for home, office, and hybrid workspace use and can also be used for a variety of purposes. However,...
|
by: aa123db |
last post by:
Variable and constants
Use var or let for variables and const fror constants.
Var foo ='bar';
Let foo ='bar';const baz ='bar';
Functions
function $name$ ($parameters$) {
}
...
|
by: ryjfgjl |
last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: Hystou |
last post by:
There are some requirements for setting up RAID:
1. The motherboard and BIOS support RAID configuration.
2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However,...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
| |
