10946 - You want what filled?

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

rambo1980
New poster
Posts: 15
Joined: Sun Mar 18, 2012 2:45 pm

Re: 10946 - You want what filled?

Post by rambo1980 » Sat Apr 21, 2012 10:46 am

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10946 - You want what filled?

Post by brianfry713 » Tue Dec 11, 2012 10:37 pm

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
Check input and AC output for thousands of problems on uDebug!

Karkat_Vantas
New poster
Posts: 4
Joined: Thu Aug 21, 2014 2:59 am

Re: 10946 - You want what filled?

Post by Karkat_Vantas » Thu Aug 21, 2014 3:01 am

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10946 - You want what filled?

Post by brianfry713 » Thu Aug 21, 2014 8:19 pm

Insert this before line 86:
if(size == h.size && let.compareTo(h.let) == 0)
return 0;
Check input and AC output for thousands of problems on uDebug!

ashdboss
New poster
Posts: 16
Joined: Fri May 17, 2013 8:59 am

Re: 10946 - You want what filled?

Post by ashdboss » Mon Sep 01, 2014 8:49 am

got AC
Last edited by ashdboss on Mon Sep 01, 2014 9:07 am, edited 1 time in total.

Zyaad Jaunnoo
Experienced poster
Posts: 122
Joined: Tue Apr 16, 2002 10:07 am

Re: 10946 - You want what filled?

Post by Zyaad Jaunnoo » Fri Oct 31, 2014 5:26 pm

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

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 10946 - You want what filled?

Post by uDebug » Mon Apr 06, 2015 6:32 pm

brianfry713, Roby and zoranh,
Thanks for the great test cases!
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

zamil.mahmud
New poster
Posts: 1
Joined: Thu Apr 30, 2015 10:48 am

Re: 10946 - You want what filled?

Post by zamil.mahmud » Thu Apr 30, 2015 10:52 am

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
New poster
Posts: 28
Joined: Thu Nov 20, 2014 9:57 pm

Re: 10946 - You want what filled?

Post by ssavi » Sun Jun 21, 2015 4:37 am

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...
I know I am a Failure Guy . :(

Post Reply

Return to “Volume 109 (10900-10999)”