Page 3 of 3

Re: 10946 - You want what filled?

Posted: Sat Apr 21, 2012 10:46 am
by 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

Re: 10946 - You want what filled?

Posted: Tue Dec 11, 2012 10:37 pm
by 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

Re: 10946 - You want what filled?

Posted: Thu Aug 21, 2014 3:01 am
by 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;}
}

Re: 10946 - You want what filled?

Posted: Thu Aug 21, 2014 8:19 pm
by brianfry713
Insert this before line 86:
if(size == h.size && let.compareTo(h.let) == 0)
return 0;

Re: 10946 - You want what filled?

Posted: Mon Sep 01, 2014 8:49 am
by ashdboss
got AC

Re: 10946 - You want what filled?

Posted: Fri Oct 31, 2014 5:26 pm
by Zyaad Jaunnoo
Consider neighbouring cells to be only to the left, right, up and down.
Not diagonally!

Re: 10946 - You want what filled?

Posted: Mon Apr 06, 2015 6:32 pm
by uDebug
brianfry713, Roby and zoranh,
Thanks for the great test cases!

Re: 10946 - You want what filled?

Posted: Thu Apr 30, 2015 10:52 am
by 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;
}

Re: 10946 - You want what filled?

Posted: Sun Jun 21, 2015 4:37 am
by 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...