Ship lenght

WilliamMorris (27)
Hi there, I need to find the ship length and return its coordinate(the end of the ship). I need to create recursive function, but it is really hard to figure it out, because the ship can be like snake(but not diagonal) and ships can't touch. I started doing something and I have a prototype, everything is good except find(recursion)function which I can't finish..
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
 
#include <iostream>
#include <string>
#include <algorithm>
#define M 10
#define N 10

using namespace std;
int row,collumn,length,row_max=0,col_max=0,length_max=0;  // e-row, s-coll, il-lenght, em-max row, sm-max col, ilm-max lenght

  char data[M][N] = {
    {'0', '0', '0', '0', '+', '+', '+', '+', '+', '+'},
    {'+', '0', '0', '0', '+', '0', '0', '0', '0', '+'},
    {'+', '0', '0', '0', '+', '0', '+', '+', '+', '+'},
    {'+', '+', '+', '+', '+', '0', '0', '0', '0','0'},
    {'0', '0', '0', '0', '0', '0', '0', '0', '0', '0'},
    {'0', '0', '0', '0', '0', '0', '0', '0', '0', '0'},
    {'0', '0','0', '0', '0', '0', '0', '0', '0', '0'},
    {'0', '+', '+', '+','+','+','+', '0', '0', '0'},
    {'0', '+', '0', '0','0', '0', '0', '0', '0', '0'},
    {'0', '+', '0', '0','0', '0', '0', '0', '0', '0'},
};





void printArr(){

    for (int i = 0; i < M; ++i) {
        cout << endl;
        for (int j = 0; j < N; ++j) {
            cout << data[i][j] << " ";
        }
    }
}
void find(int i, int j)
{
int mat [][N]={0};



    for (int i = 0; i < M; i++)
    {
        for (int j = 0; j < N; j++)
        {
            data[i][j];

            if (i || j)
            {
                // look above
                if (i > 0 && abs(mat[i - 1][j] - mat[i][j]) == 1)
                {
                    data[i][j] = max(data[i][j],data[i - 1][j] + 1);

                    if (length_max < data[i][j])
                    {
                        length_max = data[i][j];
                        row_max = i, col_max = j;
                    }
                }

                // look left
                if (j > 0 &&
                    abs(mat[i][j - 1] - mat[i][j]) == 1)
                {
                    data[i][j] = max(data[i][j],
                                       data[i][j - 1] + 1);
                    if (row_max < data[i][j])
                    {
                       row_max = data[i][j];
                        row_max = i, col_max = j;
                    }
                }
            }
        }
    }

  ///////////////////////////
/////////////////////////
////////////////////////

int main(){

    printArr();
    int i,j;
    for(i=0;i<N;i++){
     for(j=0;j<M;j++)
     {
      if(data[i][j]=='+')
            find(i,j);
     }

    }
cout<<"longest ship"<<row_max<<"  "<<col_max<<"  "<<length_max<<endl;
    return 0;
}
Golden Lizard (310)
ship can be like snake

What kind of ship looks like a snake? O_o

As for your recursive function, do a recursive flood fill, as you say ships can't touch, so that should work.
WilliamMorris (27)
What is recursive flood fill? :D But there can be more ships than 1 and can this flood fill return the last coordinte of the ship and its lenght?
Last edited on
dhayden (5798)
You may need to make a copy of the data array for this to work because the algorithm below will remove the ship locations as it finds them.

First of all, find() needs to return 2 things: the length of the ship and the location. So I'd make the prototype:
1
2
3
4
 
// Find a ship starting at i,j.  Return it's length. If non-zero,
// set loc_x and loc_y to the location
int
find(int x, int y, int &loc_x, int &loc_y)

If you see a square that is part of a ship, then mark it as empty (to avoid infinite recursion, and then see if the ship continues in the up, down, left or right direction:
1
2
3
4
5
6
7
8
9
10
 
    if (data[x][y] == '+') {
        data[x][y] = '0';
        result = 1;
        // Look up, down, left and right
        result += find(x, y-1, loc_x, loc_y);
        result += find(x, y+1, loc_x, loc_y);
        result += find(x-1, y, loc_x, loc_y);
        result += find(x+1, y, loc_x, loc_y);
    }
    return result;

Notice that I set result=1 to indicate that we've found part of a ship. Then I call find() in the up, down, left,and right directions. Find will return then length of the ship that it finds in any of those directions, so I can just add that value to the result that I already have.

This will help with the recursion, but you will need to make further changes to make this work:

Right now the code doesn't check to make sure that you're passing legal values for x and y. My advice is to add code at the beginning of the function to check if x or y is out of bounds. If it's out of bounds, just return 0: there is no ship outside the grid.

Also, this doesn't set loc_x and loc_y anywhere. Think about where to set it, and what to set it to. Here's a hint: each time you find a square containing part of a ship, you have found the furthest extreme point of the ship so far. The code to solve this is very simple, so if you find yourself writing lots of code, then stop and try again. If you can't get it in an hour or 90 minutes, then post again. There's no sense knocking yourself out over it.

This code will find a ship in the grid. You will still need to add code to the main program to keep track of the longest ship found, and where it starts.

Good luck!
WilliamMorris (27)
Should'nt it be something like that?
#include<iostream>
using namespace std;

#define M 10
#define N 10


void floodFillUtil(int screen[][N], int x, int y, int prevCoord, int newCoord)
{

if (x < 0 || x >= M || y < 0 || y >= N)
return;
if (screen[x][y] != prevCoord)
return;

// Replace the color at (x, y)
screen[x][y] = newCoord;

// Recur for north, east, south and west
floodFillUtil(screen, x+1, y, prevCoord, newCoord);
floodFillUtil(screen, x-1, y, prevCoord, newCoord);
floodFillUtil(screen, x, y+1, prevCoord, newCoord);
floodFillUtil(screen, x, y-1, prevCoord, newCoord);
}


void floodFill(int screen[][N], int x, int y, int newCoord)
{
int prevCoord = screen[x][y];
floodFillUtil(screen, x, y, prevCoord, newCoord);
}
Last edited on
dhayden (5798)
It looks to me like that will do a flood fill. Now you have to figure out how to apply that to the problem at hand.
WilliamMorris (27)
It almost works.. But there should be minor changes :D...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
 
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#define N 10
#define M 10
using namespace std;
int x,y,prevCoord,newCoord;
  char data[N][M] = {
    {'0', '0', '0', '0', '+', '+', '+', '+', '+', '+'},
    {'+', '0', '0', '0', '+', '0', '0', '0', '0', '+'},
    {'+', '0', '0', '0', '+', '0', '+', '+', '+', '+'},
    {'+', '+', '+', '+', '+', '0', '0', '0', '0','0'},
    {'0', '0', '0', '0', '0', '0', '0', '0', '0', '0'},
    {'0', '0', '0', '0', '0', '0', '0', '0', '0', '0'},
    {'0', '0','0', '0', '0', '0', '0', '0', '0', '0'},
    {'0', '+', '+', '+','+','+','+', '0', '0', '0'},
    {'0', '+', '0', '0','0', '0', '0', '0', '0', '0'},
    {'0', '+', '0', '0','0', '0', '0', '0', '0', '0'},
};





void printArr(char a[N][M]){

    for (int i = 0; i < N; ++i) {
        cout << endl;
        for (int j = 0; j < M; ++j) {
            cout << a[i][j] << " ";
        }
    }
}
void floodFillUtil(int x, int y, int prevCoord, int newCoord)
{

if (x < 0 || x >= M || y < 0 || y >= N)
return;
if (data[x][y] != prevCoord)
return;

// Replace the color at (x, y)
data[x][y] = newCoord;

// Recur for north, east, south and west
floodFillUtil( x+1, y, prevCoord, newCoord);
floodFillUtil( x-1, y, prevCoord, newCoord);
floodFillUtil( x, y+1, prevCoord, newCoord);
floodFillUtil( x, y-1, prevCoord, newCoord);
}

void floodFill( int x, int y, int newCoord)
{
int prevCoord = data[x][y];
floodFillUtil( x, y, prevCoord, newCoord);
}




int main(){
    int x,y,newcoord;

for(x=0;x<N;x++){
     for(y=0;y<M;y++)
     {
      if(data[x][y]=='+')
floodFill(x,y,newCoord);
     }

    }
cout<<"longest ship"<<"  "<<x<<"  "<<y<<"  "<<newcoord<<endl;
    return 0;
}


dhayden (5798)
Reread my first post for some ideas on how to modify floodfill() so it records the length of the ship and one endpoint.
WilliamMorris (27)
It think it should be something like this, but I don't know how to use rmax(max lenght), ymax and xmax(the longest ship coordinate)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
 
#include <iostream>
#include <string>
#include <cmath>
#define N 10
#define M 10
using namespace std;
int x,y,r,xmax,ymax,rmax;
  char data[N][M] = {
    {'0', '0', '0', '0', '+', '+', '+', '+', '+', '+'},
    {'+', '0', '0', '0', '+', '0', '0', '0', '0', '+'},
    {'+', '0', '0', '0', '+', '0', '+', '+', '+', '+'},
    {'+', '+', '+', '+', '+', '0', '0', '0', '0','0'},
    {'0', '0', '0', '0', '0', '0', '0', '0', '0', '0'},
    {'0', '0', '0', '0', '0', '0', '0', '0', '0', '0'},
    {'0', '0','0', '0', '0', '0', '0', '0', '0', '0'},
    {'0', '+', '+', '+','+','+','+', '0', '0', '0'},
    {'0', '+', '0', '0','0', '0', '0', '0', '0', '0'},
    {'0', '+', '0', '0','0', '0', '0', '0', '0', '0'},
};





void printArr(char a[N][M]){

    for (int i = 0; i < N; ++i) {
        cout << endl;
        for (int j = 0; j < M; ++j) {
            cout << data[i][j] << " ";
        }
    }
}
void findd(int x,int y)
{


 if (data[x][y] == '+') {
        r++;

if(x!=0){
 findd( x-1, y);
}
if(x!=M){
findd( x+1, y);
}
if(y!=0){

findd( x, y-1);
}
if(y!=N){
findd( x, y+1);
}
}
}
int main(){


for(int x=0;x<N;x++){
     for(int y=0;y<M;y++)
     {if(data[x][y]=='+');
         findd(x,y);

     }

    }

    return 0;

}
dhayden (5798)
Not quite. You're checking to see if a ship is present, but what's to prevent the code from doing this:
- You find a ship present. Yay!
- You check to the left and find the ship present there too. Yippee!
- You check to the right and there's a ship there too. Aright!

But that third check is for the same square as the first, so the process will continue forever. Once you find a square, you need to mark so it won't be found again. This is why I said 
1
2
3
 
if(x!=M){
findd( x+1, y);
}

That array has M elements, indexed by values 0 to M-1, so this should be:
1
2
3
 
if (x != M-1) {
    findd(x+1, y);
}

Personally, I prefer to check the bounds once at the start of the function and not worry about it when making the calls.
1
2
3
4
5
6
 
if (x<0 || x >= M || y< 0 || y >= N) return 0;
...
findd(x-1,y);
findd(x+1,y);
findd(x,y-1);
findd(x,y+1);

I don't know how to use rmax(max lenght), ymax and xmax(the longest ship coordinate)
Right now you're incrementing r inside the function. This is bad because it creates a hidden part of the interface to the function: r must be set to zero before you call it. That's why I think the interface should be:
1
2
3
4
 
// Find a ship starting at x,y.  Return it's length. If non-zero,
// set loc_x and loc_y to the location of one endpoint of the ship.
int
find(int x, int y, int &loc_x, int &loc_y)

Topic archived. No new replies allowed.