## 11520 - Fill the Square

Moderator: Board moderators

I_am_legend
New poster
Posts: 1
Joined: Fri Oct 10, 2008 8:49 pm

### 11520 - Fill the Square

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

### Re: 11520

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.

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

### Re: 11520 - Fill the Square

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 .....

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

### Re: 11520 - Fill the Square

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 ), 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

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) {

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

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++) {
}
}
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;
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);
}
}
}

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

}
}

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;

}

@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

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!