11953 - Battleships

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

Moderator: Board moderators

truewt
New poster
Posts: 6
Joined: Thu Apr 14, 2011 9:34 am

11953 - Battleships

Post by truewt » Sat Apr 16, 2011 3:52 pm

Code: Select all

omg thank you so much! super silly mistakes...
Anyone has any critical test cases? I'm running okay on the sample input, but WA.. my code shouldn't be wrong??
Last edited by truewt on Sun Apr 17, 2011 8:38 am, edited 2 times in total.

jurajz
Learning poster
Posts: 69
Joined: Sat Sep 02, 2006 7:30 pm
Location: Slovakia

Re: 11953 - Battleships

Post by jurajz » Sun Apr 17, 2011 12:32 am

Hi truewt,

I think, your output is not correct for sample input, you forgot print end of line character, so your output is only one line...

Change

Code: Select all

cout << "Case " << counter++ << ": " << ans;
to

Code: Select all

cout << "Case " << counter++ << ": " << ans << "\n";
and I hope you will get AC now. Your floodfill seems OK. Don't forget delete your code, when you will have AC :-)

truewt
New poster
Posts: 6
Joined: Thu Apr 14, 2011 9:34 am

Re: 11953 - Battleships

Post by truewt » Sun Apr 17, 2011 8:38 am

Thanks so much for the help!!! :)

Mehadi
New poster
Posts: 18
Joined: Sun Jan 24, 2010 11:17 am

11953 - Battleships(WA)

Post by Mehadi » Thu Apr 21, 2011 8:32 pm

Any one has any critical test cases?
I did not find why my code goes for WA.I think my floodfill is ok

Code: Select all

Removed After ACC
Thanks in advance

shakil
Learning poster
Posts: 74
Joined: Sat Jul 15, 2006 6:28 am
Location: CUET , bangladesh
Contact:

Re: 11953 - Battleships

Post by shakil » Sat Jun 11, 2011 8:40 pm

I also got WA. But why???

Code: Select all

#include<stdio.h>
long B[109][109],n,cas,cas1,count,i,j;
char A[109][109];

void make(long x,long y,long z,long z1)
{
B[x][y]=1;

if(z+1<=n/2)
{
if((z1==0 ||z1==1)&&x-1>=0&&('x'==A[x-1][y]||'@'==A[x-1][y])&&B[x-1][y]==0)
make(x-1,y,z+1,1);
else if((z1==0 ||z1==1)&&x+1<n&&('x'==A[x+1][y]||'@'==A[x+1][y])&&B[x+1][y]==0)
make(x+1,y,z+1,1);
else if((z1==0 ||z1==2)&&y-1>=0&&('x'==A[x][y-1]||'@'==A[x][y-1])&&B[x][y-1]==0)
make(x,y-1,z+1,2);
else if((z1==0 ||z1==2)&&y+1<n&&('x'==A[x][y+1]||'@'==A[x][y+1])&&B[x][y+1]==0)
make(x,y+1,z+1,2);
}

}

int main()
{

scanf("%ld",&cas);

for(cas1=1;cas1<=cas;cas1++)    
{
scanf("%ld",&n);

for(i=0;i<n;i++)
{
scanf("%s",A[i]);
for(j=0;j<n;j++)
B[i][j]=0;
}

count = 0;

for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(A[i][j]=='x'&&B[i][j]==0)
{
count++;
make(i,j,1,0);
}

printf("Case %ld: %ld\n",cas1,count);

}    
    
return 0;    
}
SHAKIL

Scarecrow
Learning poster
Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

Re: 11953 - Battleships

Post by Scarecrow » Sat Jul 14, 2012 12:49 am

can't find why getting WA. and the problem specification was not too clear to me. please someone help finding the bug

Code: Select all

AC
Do or do not. There is no try.

faraa_T
New poster
Posts: 8
Joined: Fri Jul 19, 2013 6:16 pm

Re: 11953 - Battleships

Post by faraa_T » Fri Jul 19, 2013 6:21 pm

Hi
Please help me
Why Runtime Error?
Thank you so much...

Code: Select all

 Deleted After AC
Last edited by faraa_T on Mon Jul 22, 2013 1:38 am, edited 1 time in total.

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

Re: 11953 - Battleships

Post by brianfry713 » Fri Jul 19, 2013 9:54 pm

From uhunt:
AKJ88> @faraa In your dfs function y+1 can exceed grid boundary. Check if it's within boundary or not, and also 'Case' has capital C.
Check input and AC output for thousands of problems on uDebug!

faraa_T
New poster
Posts: 8
Joined: Fri Jul 19, 2013 6:16 pm

Re: 11953 - Battleships

Post by faraa_T » Sat Jul 20, 2013 12:41 am

@brianfry713
Thank you so much.But I tried many test cases and It doesn't have any problem.
Please give me some test case
Tnx :)

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

Re: 11953 - Battleships

Post by brianfry713 » Sat Jul 20, 2013 9:58 am

try input

Code: Select all

1
3
x..
...
@.@
Check input and AC output for thousands of problems on uDebug!

faraa_T
New poster
Posts: 8
Joined: Fri Jul 19, 2013 6:16 pm

Re: 11953 - Battleships

Post by faraa_T » Sat Jul 20, 2013 2:39 pm

Hi.
I know what is the problem and where is it...
But I can't fix it!!! :oops:
I tried so much...
Can you help me?
(It takes me wrong answer because if the length of the ships further more n/2.It sometimes don't understand!!!!)

Code: Select all

Deleted After Ac :D 
Last edited by faraa_T on Mon Jul 22, 2013 1:39 am, edited 2 times in total.

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

Re: 11953 - Battleships

Post by brianfry713 » Sat Jul 20, 2013 5:33 pm

Use class Main
Check input and AC output for thousands of problems on uDebug!

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

Re: 11953 - Battleships

Post by brianfry713 » Sun Jul 21, 2013 12:03 pm

Try input:

Code: Select all

1
5
x....
x....
.....
.....
.....
Check input and AC output for thousands of problems on uDebug!

faraa_T
New poster
Posts: 8
Joined: Fri Jul 19, 2013 6:16 pm

Re: 11953 - Battleships

Post by faraa_T » Sun Jul 21, 2013 11:26 pm

Hi,please help me...

I tried to write my code very simple...
But time limit...!!!


class Main{

static int[][] ar = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
static char[] temp;
static char[][] grid;
static int cnt;
static boolean alive;

public static void main(String[] args) {

Scanner in = new Scanner(System.in);
int t;
t = in.nextInt();

for (int k = 0; k < t; k++) {
int n = in.nextInt();
grid = new char[n + 2][n + 2];
cnt = 0;
in.nextLine();

for (int i = 0; i < n; i++) {
String line = in.nextLine();
temp = line.toCharArray();
for(int j=0;j<temp.length;j++){
grid[i+1][j+1]=temp[j];
}
}

for (int i = 1; i < grid.length - 1; i++) {
for (int j = 1; j < grid.length - 1; j++) {
if (grid[j] == 'x') {
cnt++;
dfs(i, j);
}
}
}

int ans = k + 1;
System.out.println("Case " + ans + ": " + cnt);
}
}

public static void dfs(int x, int y) {
if (x == (grid.length - 1) || y == (grid.length - 1) || x == 0 || y == 0 || grid[x][y] == '.') {
return;
}

grid[x][y] = '.';

for (int i = 0; i < ar.length; i++) {
int r = x + ar[0];
int c = x + ar[1];
dfs(r, c);

}
}
}

shuvokr
Learning poster
Posts: 66
Joined: Tue Oct 02, 2012 8:16 pm
Location: Bangladesh

Re: 11953 - Battleships

Post by shuvokr » Mon Jul 22, 2013 1:05 am

faraa in your DFS funcyion

Code: Select all

for (int i = 0; i < ar.length; i++)
 {
          int r = x + ar[i][0];
          int c = x + ar[i][1];
          dfs(r, c);
}
It's should be

Code: Select all

for (int i = 0; i < ar.length; i++)
 {
          int r = x + ar[i][0];
          int c = y + ar[i][1];
          dfs(r, c);
}
Am i right ? :)

Code: Select all

enjoying life ..... 

Post Reply

Return to “Volume 119 (11900-11999)”