11520 - Fill the Square

All about problems in Volume 115. 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
I_am_legend
New poster
Posts: 1
Joined: Fri Oct 10, 2008 8:49 pm

11520 - Fill the Square

Post by I_am_legend » Thu Nov 06, 2008 1:47 am

I am getting wa for this easy prob..but why??? please anyone help me...
this is my code
[*# include <stdio.h>
# include <ctype.h>

int i,j,row_col;
char grid[10][10];

char which_letter(void);

int main()
{
int n,cn;
char ch;

scanf("%d",&n);
for(cn = 1 ; cn <= n ;cn++)
{
scanf("%d",&row_col);
scanf("%c",&ch);

for(i = 0;i<row_col;i++)
gets(grid);

for(i=0;i<row_col;i++)
for(j=0;j<row_col;j++)
if(grid[j]=='.')
grid[j] = which_letter();


printf("Case %d:\n",cn);
for(i = 0;i<row_col;i++)
puts(grid);
for(i=0;i<row_col;i++)
for(j=0;j<row_col;j++)
grid[j] = '\0';
}
return 0;
}


char which_letter(void)
{
char k,left,right,up,down;

left = right = up = down = ('A'-1);

if(isupper(grid[j-1]))
left = grid[j-1];
if(isupper(grid[i-1][j]))
up = grid[i-1][j];
if(isupper(grid[i+1][j]))
down = grid[i+1][j];
if(isupper(grid[j+1]))
right =grid[j+1];

for(k = 'A';;k++)
if(left != k && right != k && up != k && down != k)
return k;
}

]

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 11520

Post by Obaida » Mon Nov 10, 2008 7:35 am

To I_am_legend you should get RTE also. You r using a small array!
I can't understand why i am wa!!!!

Code: Select all

#include<stdio.h>
int main()
{
	int c,n,i,j,ca=0,ce;
	char st[20][20];
	scanf("%d",&ce);
	while(ce--)
	{
		ca++;
		scanf("%d",&n);
		getchar();
		for(i=0;i<n;i++)
		{
			for(j=0;j<n;j++)
			{
				scanf("%c",&st[i][j]);
			}
			getchar();
		}
		printf("Case %d:\n",ca);
		for(i=0;i<n;i++)
		{
			for(j=0;j<n;j++)
			{
				c=65;
				if(i==0&&j==0)
				{
					while(st[i][j+1]==c||st[i+1][j]==c)
					{
						c++;
					}
					st[i][j]=c;
					printf("%c",c);
				}
				else if(i==n-1&&j==n-1)
				{
					while(st[i][j-1]==c||st[i-1][j]==c)
					{
						c++;
					}
					st[i][j]=c;
					printf("%c",c);
				}
				else if(i==0&&j==n-1)
				{
					while(st[i][j-1]==c||st[i+1][j]==c)
					{
						c++;
					}
					st[i][j]=c;
					printf("%c",c);
				}
				else if(i==n-1&&j==0)
				{
					while(st[i][j+1]==c||st[i-1][j]==c)
					{
						c++;
					}
					st[i][j]=c;
					printf("%c",c);
				}
				else if(i==0)
				{
					while(st[i][j-1]==c||st[i][j+1]==c||st[i+1][j]==c)
					{
						c++;
					}
					st[i][j]=c;
					printf("%c",c);
				}
				else if(i==n-1)
				{
					while(st[i][j+1]==c||st[i][j-1]==c||st[i-1][j]==c)
					{
						c++;
					}
					st[i][j]=c;
					printf("%c",c);
				}
				else if(j==0)
				{
					while(st[i+1][j]==c||st[i-1][j]==c||st[i][j+1]==c)
					{
						c++;
					}
					st[i][j]=c;
					printf("%c",c);
				}
				else if(j==n-1)
				{
					while(st[i+1][j]==c||st[i-1][j]==c||st[i][j-1]==c)
					{
						c++;
					}
					st[i][j]=c;
					printf("%c",c);
				}
				else
				{
					while(st[i][j+1]==c||st[i][j-1]==c||st[i+1][j]==c||st[i-1][j]==c)
					{
						c++;
					}
					st[i][j]=c;
					printf("%c",c);
				}
			}
			puts("");
		}
	}
	return 0;
}
try_try_try_try_&&&_try@try.com
This may be the address of success.

User avatar
shaon_cse_cu08
New poster
Posts: 50
Joined: Tue May 25, 2010 9:10 am
Contact:

Re: 11520 - Fill the Square

Post by shaon_cse_cu08 » Thu Aug 19, 2010 2:00 pm

Obaida here is some case for u....

Input:
2
2
A.
A.
3
A.B
ABB
.B.

Output:

Case 1:
AB
AC
Case 2:
ACB
ABB
CBA

But ur program replaces AB to Ba...
You should only substitute the '.' with characters lexicographically....

And u can do this with only one if() statement... just check before,after,upper and lower cell of ur array where there is a '.' and fill it with characters...

Every 1 should think differently...Thus we may able to make a difference
:)
I'll keep holding on...Until the walls come tumbling down...And freedom is all around ..... :x

User avatar
plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

Re: 11520 - Fill the Square

Post by plamplam » Sun Jun 26, 2011 11:10 pm

Try these cases:

Code: Select all

5
1
.
1
Z
2
DA
B.
3
BBC
C.D
LAL
3
XAY
W.W
ABA

Code: Select all

Case 1:
A
Case 2:
Z
Case 3:
DA
BC
Case 4:
BBC
CED
LAL
Case 5:
XAY
WCW
ABA
P.S The judge data sucks, I know my program gives wrong output for some particular input/s(which I found out at the time of writing this post :P), but I got AC in first try:)
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

sith
Learning poster
Posts: 72
Joined: Sat May 19, 2012 7:46 pm

Re: 11520 - Fill the Square

Post by sith » Thu Dec 06, 2012 9:24 am

Hi,

I've got WA, but my solution shows correct results for mentioned inputs.
Why WA? Maybe I print extra '\n', or there are any special case that I missed?

Code: Select all

import java.io.*;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;

class Main {


    public static void main(String[] args) {


        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));


        Scanner scanner = new Scanner(reader);
        try {
            int cases = scanner.nextInt();

            for (int i = 1; i <= cases; i++) {

                int n = scanner.nextInt();

                Board board = new Board(n);

                for (int j = 0; j < n; j++) {
                    String next = scanner.next();
                    char[] chars = next.toCharArray();
                    for (int k = 0; k < n; k++) {
                        board.addPoint(j, k, chars[k]);
                    }
                }
                writer.write(String.format("Case %d:\n", i));
                Backtrack backtrack = new Backtrack(writer);
                backtrack.backtrack(new Character[board.n * board.n + 1], board, 0);
            }
            writer.flush();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    static class Backtrack {
        boolean finished = false;
        private BufferedWriter writer;

        public Backtrack(BufferedWriter writer) {
            this.writer = writer;
        }

        private void backtrack(Character[] a, Board board, int k) throws IOException {

            if (isSolution(board)) {
                board.printBoard(writer);
                finished = true;
            } else {
                k++;
                Point nextPoint = board.candidates.iterator().next();
                Set<Character> candidates = nextPoint.candidates;

                Character[] candidatesArray = new Character[candidates.size()];
                candidates.toArray(candidatesArray);


                for (Character candidate : candidatesArray) {
                    a[k] = candidate;
                    board.addPoint(nextPoint.r, nextPoint.c, candidate);
                    backtrack(a, board, k);
                    board.restorePoint(nextPoint.r, nextPoint.c);

                    if (finished) {
                        return;
                    }
                }
            }
        }


        private boolean isSolution(Board board) {
            return board.candidates.size() == 0;
        }
    }


    static class Board {

        private final Point[][] points;
        private int n;

        Set<Point> candidates = new TreeSet<Point>();

        Board(int n) {
            this.n = n;

            points = new Point[n][n];
            for (int j = 0; j < points.length; j++) {
                Point[] row = points[j];
                for (int i = 0; i < row.length; i++) {
                    points[j][i] = new Point('.', j, i);
                    candidates.add(points[j][i]);
                }
            }
        }

        public void addPoint(int r, int c, char value) {

            Point point = points[r][c];
            point.value = value;

            if (value != '.') {
                updateCandidates(r, c, value);
                candidates.remove(point);
            }
        }

        public void restorePoint(int r, int c) {

            char value = points[r][c].value;
            points[r][c].value = '.';

            updateCandidate(r, c, value);
            updateCandidate(r - 1, c, value);
            updateCandidate(r + 1, c, value);
            updateCandidate(r, c - 1, value);
            updateCandidate(r, c + 1, value);
        }

        private void updateCandidate(int r, int c, char value) {

            if (r < 0 || r >= n || c < 0 || c >= n) {
                return;
            }

            if (isAcceptedCadidate(r, c, value)) {
                points[r][c].candidates.add(value);
                candidates.add(points[r][c]);
            }
        }

        private boolean isAcceptedCadidate(int r, int c, char value) {

            if (r - 1 >= 0 && points[r - 1][c].candidates.contains(value)) {
                return false;
            }
            if (r + 1 < n && points[r + 1][c].candidates.contains(value)) {
                return false;
            }
            if (c - 1 >= 0 && points[r][c - 1].candidates.contains(value)) {
                return false;
            }
            if (c + 1 < n && points[r][c + 1].candidates.contains(value)) {
                return false;
            }
            return true;

        }

        public void printBoard(BufferedWriter writer) throws IOException {
            for (Point[] row : points) {
                for (Point point : row) {
                    writer.write(Character.toString(point.value));
                }
                writer.write("\n");
            }
        }

        private void updateCandidates(int r, int c, char value) {
            points[r][c].candidates.remove(value);

            if (r - 1 >= 0) {
                points[r - 1][c].candidates.remove(value);
            }
            if (r + 1 < n) {
                points[r + 1][c].candidates.remove(value);
            }
            if (c - 1 >= 0) {
                points[r][c - 1].candidates.remove(value);
            }
            if (c + 1 < n) {
                points[r][c + 1].candidates.remove(value);
            }
        }
    }

    static class Point implements Comparable<Point> {

        char value;
        int r, c;
        Set<Character> candidates = new TreeSet<Character>();


        Point(char value, int r, int c) {
            this.value = value;
            this.r = r;
            this.c = c;

            candidates.add('A');
            candidates.add('B');
            candidates.add('C');
            candidates.add('D');
            candidates.add('E');
            candidates.add('F');
            candidates.add('G');
            candidates.add('H');
            candidates.add('I');
            candidates.add('J');
            candidates.add('K');
            candidates.add('M');
            candidates.add('N');
            candidates.add('O');
            candidates.add('P');
            candidates.add('Q');
            candidates.add('R');
            candidates.add('S');
            candidates.add('T');
            candidates.add('U');
            candidates.add('V');
            candidates.add('W');
            candidates.add('X');
            candidates.add('Y');
            candidates.add('Z');

        }

        @Override
        public int compareTo(Point o) {
            int sizeDiff = candidates.size() - o.candidates.size();
            if (sizeDiff != 0) {
                return sizeDiff;
            }
            int rowDiff = r - o.r;
            if (rowDiff != 0) {
                return rowDiff;
            }
            return c - o.c;
        }
    }
}

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

Re: 11520 - Fill the Square

Post by brianfry713 » Sat Dec 08, 2012 7:56 am

Input:

Code: Select all

2
3
..B
...
...
3
B..
...
..A
Correct output:

Code: Select all

Case 1:
ACB
BAC
ABA
Case 2:
BAB
ABC
BCA
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 115 (11500-11599)”