Depth priority search questions (game programming practice)

Asked 1 years ago, Updated 1 years ago, 93 views

I'm solving the past questions of competition programming, but I don't get the output I expected from the test case.
Why?
This problem seems to be a problem for all exploration, so I try to solve it using depth priority exploration, but it shows a different value than the answer.

Problem B: How many islands are there?

For this problem, a mesh-like map separated into squares of the same size is given.
This map represents an area of sea where each square corresponds to land or sea. Figure B-1 is an example of a map.

Figure b-1
Figure B-1: Map of a certain sea area

If two land-corresponding square areas adjoin each other vertically, horizontally, or diagonally on a map, you can walk from one side to the other.
Two land-corresponding territories belong to the same island only when one can walk from one island to the other (generally via another land).
Also, the waters on this map are surrounded by the sea and cannot be walked out of it.

I want you to read the given map and create a program to count how many islands there are in this area. For example, the map in Figure B-1 has three islands in total.
Input

Inputs are columns of data sets, each of which is given in the following format.

wh
c1,1 c1,2...c1,w
c2,1 c2,2...c2,w
...
ch,1 ch,2...ch,w

w and h are positive integers of 50 or less representing the width and height of the map, and the map consists of w×h squares of the same size. w and h
The space between is separated by a single blank character.

If ci,j is 0 or 1 and separated by one blank character.ci,j = 0, it is the ith from the left on the map and j
from the top. The third square is the sea, where ci,j = 1 is land.

The end of the input is represented by a line of only two zeros separated by one blank character.

#include<bits/stdc++.h>

int dx[ ] = {1,0,-1,1,-1,1,0,-1};
intdy[] = {1,1,1,0,0,-1,-1,-1};
int w,h,c;

void dfs(intx, inty, std::vector<std::vector<int>map, std::vector<std::vector>bool>>>>visited, int&c){
    pool new_land; 
    if(visited[y][x]) {//visited contains where already visited.
        return;
    }
    visited[y][x]=true;
    if(map[y][x]==1){
        new_land = true; // this is may new land.
    }
    else{
        new_land=false;//this is sea
    }
    for(inti=0;i<8;i++){
        int cx=x+dx[i];
        intcy=y+dy[i];
        if(cx>=w||cx<0||cy<0||cy>=h){
            continue;
        }
        if(map[cy][cx]==1&visited[cy][cx]){
            // This land is connected by another land that already visited (counted).
            new_land=false;
        }
    }
    if(new_land) { // if this land is new one: increment counter(intc);
        c++;
    }
    for(inti=0;i<8;i++){
        int cx=x+dx[i];
        intcy=y+dy[i];
        if(cx>=w||cx<0||cy>=h||cy<0||visited[cy][cx]){
            continue;
        }
        dfs(cx,cy,map,visited,c);
    }
}



int main() {
    while(true){
        std::cin>>w>>h;
        if(w==0&h==0){
            break;
        }
        c=0;// reset counter for new map;
        std::vector<std::vector<int>>vec(h,std::vector<int>(w,0));
        std::vector<std::vector<bool>>bools(h,std::vector<bool>(w, false));
        for(inti=0;i<h;i++){
            for(intp=0;p<w;p++){
                std::cin>>vec[i][p];
            }
        }
        dfs(0,0,vec,bools,c);
        std::cout<<c<<std::endl;
    }
}

c++ algorithm

2022-09-30 21:40

1 Answers

Determine if the island has already been counted

 if(map[cy][cx]==1&visited[cy][cx]){
        // This land is connected by another land that already visited (counted).
        new_land=false;
    }

This code is not sufficient as it is.
For example,

33
1 1 1
0 0 1
0 0 1

In these test cases, the island is counted twice, x:0, y:0 and x:2, y:2.(where x:2, y:2, map[1][2]==1, but visited[1][2]is false)

Another example is

35
1 0 1
1 0 1
1 0 1
1 0 1
0 1 0

In these test cases, x:0, y:0 and x:2, y:0 cannot be determined to be the same island until x:1, y:4 is explored.In some cases, as in this example, it is not possible to determine if the land near you is the same island until you examine whether the trout is land or not.
In other words, it is fundamentally impossible to determine whether an island has already been counted by looking at the adjacent squares in the current code-like flow.We need to review the overall flow.


2022-09-30 21:40

If you have any answers or tips


© 2024 OneMinuteCode. All rights reserved.