11953 - Battleships

[truewt]

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

[jurajz]

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]

Thanks so much for the help!!!

[Mehadi]

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]

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

[Scarecrow]

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

[faraa_T]

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

Code: Select all

 Deleted After AC

[brianfry713]

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.

[faraa_T]

@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]

try input

Code: Select all

1
3
x..
...
@.@

[faraa_T]

Hi.
I know what is the problem and where is it...
But I can't fix it!!!
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 

[brianfry713]

Use class Main

[brianfry713]

Try input:

Code: Select all

1
5
x....
x....
.....
.....
.....

[faraa_T]

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]

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 ?