10946 - You want what filled?

[rambo1980]

I'm frustrated with this problem. I use a straightforward approach of DFS and mark all the nodes that are traversed with '.'
My code works totally fine with the testcases i've found on the board. Please anyone help me out. Why am i getting WA? Here'r my code-

Code: Select all

GOT AC

this is weird! In the problem it was said that

The first line will contain two numbers x and y, followed by x lines of y characters each. (x and y are less than 50).

at first my initial array sizes were set based on this( array[52][52] ), i was getting RTE, then i changed it to array[100][100], started getting WA. Finally I tried submitting it with array[500][500] and got AC :-\

I had to waste an entire hour trying to find out where i went wrong. This is insane :-S

[brianfry713]

Input:

Code: Select all

2 2
DC
BA
0 0

AC output:

Code: Select all

Problem 1:
A 1
B 1
C 1
D 1

[Karkat_Vantas]

My code has worked for all the sample IO posted here, but It get RuntimeError upon submit. Are there any special cases where that could occur? Thank you.

Code: Select all

import java.util.*;

 class Main implements Comparable<Main> {
	 static ArrayList<Main> ans=new ArrayList<Main>();
	 static int width;
	 static int height;
	 static String[][] map;
	 static boolean[][] used;
	 static int currentSize=0;
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		height = in.nextInt();
		width=in.nextInt();
		ans.clear();
		String temp;
		int tr=1;
		while(height!=0||width!=0)
		{
			System.out.println("Problem "+tr+":");
			map=new String[height][width];
			used=new boolean[height][width];
			for(int i=0;i<height;i++)
			{
				temp=in.next();
				for(int q=0;q<width;q++)
					map[i][q]=temp.substring(q,q+1);
			}
			for(int i=0;i<height;i++)
				for(int j=0;j<width;j++)
					{fill(i,j,map[i][j]);
					if(currentSize!=0)
						ans.add(new Main(currentSize,map[i][j]));
					currentSize=0;
					}
			Collections.sort(ans);
			for(Main h:ans)
				System.out.println(h.getLet()+" "+h.getSize());
			height=in.nextInt();
			width=in.nextInt();
			ans.clear();
			tr++;
		}
	}
	
	public static void fill(int i, int j,String x)
	{
		if(x.equals("."))
		{	used[i][j]=true;
			return;}
		if(used[i][j]==true)
			return;
		
		if(map[i][j].compareTo(x)!=0)
			return;
		used[i][j]=true;
		currentSize++;
		for(int q=-1;q<=1;q++)
			for(int w=-1;w<=1;w++)
			{
				if(Math.abs(w)+Math.abs(q)==1)
				{
					if((i+q>=0)&&(i+q<height)&&(j+w>=0)&&(j+w<width))
					{
						fill(i+q,j+w,x);
					}
						
					
					
				}
			}
		
		
	}


	private int size;
	private String let;
	public Main(int s, String x)
	{
		size=s;
		let=x;
	}
	
	public int compareTo(Main h)
	{
		if(size>h.size)
			return -1;
		else if(size==h.size)
			if(let.compareTo(h.let)<=0)
				return -1;
		
		return 1;
			
	}
	public int getSize(){return size;}
	public String getLet(){return let;}
}

[brianfry713]

Insert this before line 86:
if(size == h.size && let.compareTo(h.let) == 0)
return 0;

[ashdboss]

got AC

[Zyaad Jaunnoo]

Consider neighbouring cells to be only to the left, right, up and down.
Not diagonally!

[uDebug]

brianfry713, Roby and zoranh,
Thanks for the great test cases!

[zamil.mahmud]

Hello
This is my first post as I'm facing Wrong Answer for 10946. I put my code below. Can someone checks, why I am getting Wrong Answer.

Code: Select all

#include<stdio.h>
#include<stdlib.h>

typedef int (*compfn)(const void *, const void *);
int X,Y,holeCount=0,stCount=0,problemNo=1;
char A[500][500];

struct res{
	char key;
	int value;
}result[500];

int compare(struct res *element1, struct res *element2){
	if(element1->value < element2->value)
		return 1;
	else if(element1->value > element2->value)
		return -1;
	else if(element1->value == element2->value && element1->key < element2->key)
		return -1;
}

void floodFill(int xpos, int ypos, char CH){

	if(xpos<0 || xpos>=X || ypos<0 || ypos>=Y)
		return;
	if(A[xpos][ypos]!=CH)
		return;
	A[xpos][ypos]='.';

	holeCount++;

	floodFill(xpos-1,ypos,CH);
	floodFill(xpos,ypos-1,CH);
	floodFill(xpos,ypos+1,CH);
	floodFill(xpos+1,ypos,CH);
}

void callFloodFill(char ch){
	int count=0,i,j;

	for(i=0;i<X;i++)
	{
		for(j=0;j<Y;j++)
		{
			if(A[i][j]==ch)
			{
				holeCount=0;
				floodFill(i,j,ch);
				result[++stCount].key = ch;
				result[stCount].value = holeCount;
			}
		}
	}

}

void readInput(){
	int i;
	for(i=0;i<X;i++){
		scanf("%s",&A[i]);
	}
}

void resetStruct(){
	int i;
	stCount = 0;
	holeCount = 0;

	for(i=0;i<500;i++){
		result[i].key = '\0';
		result[i].value = 0;
	}
}

void processCase(){
	int i;

	for(i=0;i<26;i++){
		callFloodFill(65+i);
	}
}

void printSolution(){
	int i;
	printf("Problem %d:\n",problemNo++);
	for(i=0;i<500;i++){
		if(result[i].value==0)
			break;

		printf("%c %d\n",result[i].key,result[i].value);
	}
}

int main(){

	while(scanf("%d %d",&X,&Y)==2 && X!=0 && Y!=0){
		readInput();
		resetStruct();
		processCase();
		qsort((void*) &result,500,sizeof(struct res),(compfn)compare);
		printSolution();
	}
	return 0;
}

[ssavi]

Code: Select all

#include<bits/stdc++.h>
#define pii pair<int , int>

using namespace std;

char graph[100][100], ch;

int m, n;
int fx[]={0, 0, 1, -1};
int fy[]={1, -1, 0, 0};

struct matrix{
 int s;
 char p;
}g[100];

bool cmp(matrix left, matrix right)
{
    if(left.s==right.s)
        return left.p<right.p;
    return left.s>right.s;
}

int bfs(int x, int y)
{
    int cell = 0;
    queue<pii>q;
    q.push(pii(x,y));
    graph[x][y]='.';
    while(!q.empty())
    {
        cell++;
        pii top = q.front();
        q.pop();
        for(int i=0; i<4; i++)
        {
            int f = top.first + fx[i];
            int s = top.second + fy[i];
            if((f>=0 && f<m) && (s>=0 && s<n) && graph[f][s]==ch)
            {
                graph[f][s]='.';
                q.push(pii(f,s));
            }
        }
    }
    return cell;
}

int main()
{
    int t = 0;
    while(scanf("%d %d",&m,&n)==2)
    {
        if(m==0 && n==0)  break;
        getchar();
        for(int i=0; i<m; i++)
        {
            gets(graph[i]);
        }
        int f = 0;
        for(int i=0; i<m; i++)
        {
            for(int j=0; j<n; j++)
            {
                if(graph[i][j]!='.')
                {
                    ch = graph[i][j];
                    g[f].p = ch;
                    //bfs(i,j);
                    g[f].s = bfs(i,j);
                    f++;
                }
            }
        }
        sort(g,g+f,cmp);
        printf("Problem %d:\n",++t);
        for(int i=0; i<f; i++)
            printf("%c %d\n", g[i].p, g[i].s);
        for(int i=0; i<=f; i++)
        {
            g[i].p='\0';
            g[i].s=0;
        }
    }
    return 0;
}

Why it is Wrong Answer?? All the inputs of uDebug is correct...