Lượm nhặt 1 số bài test thuật toán mời ae vào giải cho vui :D - vozForums
vozForums
Go Back   vozForums > Học tập và công việc > Ngành CNTT > Phát triển Phần mềm
Reply
 
Thread Tools
  #1  
Old 15-10-2019, 18:18
liekata liekata is offline
Junior Member
 
Join Date: 02-2010
Location: Hà Nội
Posts: 15
Talking Lượm nhặt 1 số bài test thuật toán mời ae vào giải cho vui :D

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.
Reply With Quote
  #2  
Old 15-10-2019, 18:31
foreveralone's Avatar
foreveralone foreveralone is offline
Senior Member
 
Join Date: 07-2011
Posts: 509
Re: Lượm nhặt 1 số bài test thuật toán mời ae vào giải cho vui :D

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.
Reply With Quote
  #3  
Old 15-10-2019, 18:47
Nipin Nipin is offline
Senior Member
 
Join Date: 03-2018
Posts: 1,343
Re: Lượm nhặt 1 số bài test thuật toán mời ae vào giải cho vui :D

ờ sắp đến tháng 12 rồi đấy, chủ thread có tham gia advent of code 2019 không )
Reply With Quote
  #4  
Old 15-10-2019, 19:49
Blanic Blanic is offline
Đã tốn tiền
 
Join Date: 08-2013
Posts: 264
Re: Lượm nhặt 1 số bài test thuật toán mời ae vào giải cho vui :D

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
Reply With Quote
Đang tải...
  #5  
Old 16-10-2019, 10:37
liekata liekata is offline
Junior Member
 
Join Date: 02-2010
Location: Hà Nội
Posts: 15
Re: Lượm nhặt 1 số bài test thuật toán mời ae vào giải cho vui :D

Quote:
Originally Posted by foreveralone View Post
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
Reply With Quote
  #6  
Old 16-10-2019, 11:00
foreveralone's Avatar
foreveralone foreveralone is offline
Senior Member
 
Join Date: 07-2011
Posts: 509
Re: Lượm nhặt 1 số bài test thuật toán mời ae vào giải cho vui :D

Quote:
Originally Posted by liekata View Post
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
Reply With Quote
  #7  
Old 16-10-2019, 15:36
r0ut1n3 r0ut1n3 is offline
Member
 
Join Date: 12-2016
Posts: 32
Re: Lượm nhặt 1 số bài test thuật toán mời ae vào giải cho vui :D

Chuẩn miền liên thông rồi
Reply With Quote
  #8  
Old 24-10-2019, 22:42
70570020 70570020 is offline
Senior Member
 
Join Date: 06-2011
Posts: 366
Re: Lượm nhặt 1 số bài test thuật toán mời ae vào giải cho vui :D

Bookmark nghiên cứu sau
Reply With Quote
  #9  
Old 25-10-2019, 10:08
MeoMun95 MeoMun95 is offline
Junior Member
 
Join Date: 08-2014
Posts: 29
Re: Lượm nhặt 1 số bài test thuật toán mời ae vào giải cho vui :D

Code:
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
Reply With Quote
  #10  
Old 25-10-2019, 10:42
Nipin Nipin is offline
Senior Member
 
Join Date: 03-2018
Posts: 1,343
Re: Lượm nhặt 1 số bài test thuật toán mời ae vào giải cho vui :D

^:

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

Code:
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ì đó
Reply With Quote
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump

All times are GMT +7. The time now is 06:04.
Chịu trách nhiệm nội dung: Bạch Thành Trung © 2019 Công ty TNHH Thật Vi Diệu
ĐC tầng 4, số 6-8 Đường D2, Bình Thạnh, Hồ Chí Minh, Việt Nam - SĐT 0981323799 - MST 0313906593
Giấy phép thiết lập MXH số 334/GP-BTTTT, Ký ngày: 19/08/2019