UVa 11953 Battleships

Đề bài: https://uva.onlinejudge.org/external/119/11953.pdf

Abridge: Tìm các connected component (CC) trong grid, CC chứa 'x' hoặc '@'. Chú ý, một CC phải chứa ít nhất 1 kí tự 'x' thì mới được xem là con tàu (ship) còn sống và con tàu có thể nằm theo chiều ngang (horizontally), chiều dọc (vertically) hoặc kết hợp (hình chữ T).

Ý tưởng: Kết hợp dfs + đếm số CC (numCC)
Ta floodfill cho 'x' và '@', sau đó dùng numCC để đếm, nhớ là phải xuất phát tại grid[i][j]='x' vì phải chứa 'x' thì mới được xem là còn sống

Code:

Comments

  1. ```
    int ans=0;
    for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
    if(grid[i][j]=='x'){
    ans++;
    floodfill(i,j);
    }
    }
    }
    ```
    cho nay sao v ban, minh ko hieu

    ReplyDelete

Post a Comment

Popular posts from this blog

UVa 10305 Ordering Tasks