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:
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:
blog kha bo ich
ReplyDelete```
ReplyDeleteint 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