[liekata]

Hi các bác, em đang trong giai đoạn trau dồi thêm kiến thức với mong muốn làm remote cho mấy a US.
Cơ mà bọn này test nó toàn lôi thuật toán ra khè nhau, mà món này nói thực em dùng ko nhiều nên ngu lắm.

Nay em muốn nhờ ae chỉ chút đường đi nước bước với lại có vài bài thuật toán tặng các bác. Mời các bác xuất chiêu a

Đề:
Cho ma trận string [m][n] với m, n là số nguyên > 0.
Ma trận này random các giá trị là 1 và 0.
Định nghĩa: 1 là người, 0 là tường.
Với những người đứng gần nhau thì được coi là 1 nhóm, 1 người cũng được coi là 1 nhóm.
Khoảng không bên ngoài ma trận coi là tường.
==> Tìm số lượng nhóm người có trong mảng?

VD:
string[4][5]:
1 0 0 1 1
1 0 0 0 1
1 0 1 0 0
1 1 1 0 1

-> ở đây có 3 nhóm người.

[foreveralone]

Bài này là căn bản của thuật toán duyệt đồ thị. Bạn đọc về DFS và BFS là sẽ giải được.

[Nipin]

ờ sắp đến tháng 12 rồi đấy, chủ thread có tham gia advent of code 2019 không )

[Blanic]

Kiểu bài này 20 năm trước mấy ông thầy ôn cấp 2 toàn gọi là giải thuật Loang. Và nhóm gọi là miền liên thông.

Nhớ vãi :(

Sent from my iPhone using vozForums

[liekata]

Originally Posted by foreveralone

Bài này là căn bản của thuật toán duyệt đồ thị. Bạn đọc về DFS và BFS là sẽ giải được.

Thank bác chỉ giáo. Em đang tìm hiểu a.
Hiện tại cách e đang dùng là:
1. - với mỗi người ("1") sẽ check những người liền kề, và đệ quy ở đây để check toàn bộ
2. - khi không còn liền kề (trên, dưới, trái, phải) -> là kết thúc một nhóm
3. - lưu lại thông tin nhóm này vào ignore list để bỏ qua cho lần search tiếp
4. - làm lại với bước 1 và check trong ignore list

[foreveralone]

Originally Posted by liekata

Thank bác chỉ giáo. Em đang tìm hiểu a.
Hiện tại cách e đang dùng là:
1. - với mỗi người ("1") sẽ check những người liền kề, và đệ quy ở đây để check toàn bộ
2. - khi không còn liền kề (trên, dưới, trái, phải) -> là kết thúc một nhóm
3. - lưu lại thông tin nhóm này vào ignore list để bỏ qua cho lần search tiếp
4. - làm lại với bước 1 và check trong ignore list

Đúng , đó là bạn đã dùng DFS. Giải xong thì giải lại lần nữa bằng BFS nữa cho lên tay

[r0ut1n3]

Chuẩn miền liên thông rồi

[70570020]

Bookmark nghiên cứu sau

[MeoMun95]

package main

import "fmt"

func dfs(matrix [][]int, row, col int) {
	if matrix[row][col] == 0 {
		return
	}
	matrix[row][col] = 0

	if row >= 1 && matrix[row-1][col] == 1 {
		dfs(matrix, row-1, col)
	}

	if row < len(matrix)-1 && matrix[row+1][col] == 1 {
		dfs(matrix, row+1, col)
	}

	if col > 0 && matrix[row][col-1] == 1 {
		dfs(matrix, row, col-1)
	}

	if col < len(matrix[0])-1 && matrix[row][col+1] == 1 {
		dfs(matrix, row, col+1)
	}
}

func findNumberOfGroup(matrix [][]int) int {
	var result int
	for i := 0; i < len(matrix); i++ {
		for j := 0; j < len(matrix[i]); j++ {
			if matrix[i][j] == 1 {
				dfs(matrix, i, j)
				result++
			}
		}
	}
	return result
}

func main() {
	fmt.Println(findNumberOfGroup(
		[][]int{
			[]int{1, 0, 0, 1, 1},
			[]int{1, 0, 0, 0, 1},
			[]int{1, 0, 1, 0, 0},
			[]int{1, 1, 1, 0, 1},
		},
	))
}

Bài này sử dụng DFS nha mọi người, duyệt array 2 chiều, nếu phần tử nào là 1 thì duyệt DFS cho đến khi không gặp 1 nữa thì return

[Nipin]

^:

có thể viết lại cái dfs thế này:

func dfs(matrix [][]int, row, col int) {
	if row < 0 || row >= len(matrix) { return }
        if col < 0 || col >= len(matrix[0]) { return }
	if matrix[row][col] == 0 { return }

	matrix[row][col] = 0
        dfs(matrix, row-1, col)
	dfs(matrix, row+1, col)
	dfs(matrix, row, col-1)
	dfs(matrix, row, col+1)	
}

mà bước tiếp theo bạn nên cân nhắc việc khử đệ quy, dùng stack, queue hay deque gì đó