Cho 1 ma trận chứa 1 con robot và các vết bẩn, hãy tính số bước đi tối thiểu để con robot có thể lau hết tất cả các vết bẩn này. Giải thuật: Bài này chúng ta có 1 điểm bắt đầu và N điểm cần đi qua. - Không thể xác định điểm nào sẽ đi đầu tiên để số bước đi là lớn nhất vì vậy với N + 1 điểm. Hãy xây dựng ma trận N+1 x N+1. Với i và j thuộc N+1 điểm thì giá trị của ma trận [i][j] chính là đường đi ngắn nhất từ i đến j. - Việc tính toán đường đi ngắn nhất từ i đến j có thể thông qua thuật toán BFS. cụ thể ở đây ta sẽ tạo ra N+1 bảng BFS tương ứng với N+1 điểm này. Solution
Cho 28 quân bài domino được đánh nhãn (0,0),(0,1),(0,2),(0,3),(0,4),(0,5),(0,6), (1,1),(1,2),...,(5,5),(5,6),(6,6) và ma trận 8x8 chứa các số. Hãy tìm ra số lượng cách đặt các quân bài domino để phủ kín ma trận và các quân bài domino chỉ được sử dụng 1 lần. Giải thuật: - Mỗi quân bài domino có thể đặt theo chiều ngang và chiều dọc. - Dùng 1 ma trận để kiểm tra quân domino đó đã được dùng hay chưa. - Quân domino (x,y) luôn có x<=y vì vậy khi đặt quân domino hãy tìm ra giá trị min của 2 số đó. Cho 1 mê cung chứa kim cương. Hãy kiểm tra xem với số lượng cọc mà Jarmtin có thể vượt qua từ đầu bài, kiểm tra xem Jarmtin có thể lấy được kim cương và thoát ra khỏi mê cung được hay không. Đầu tiên Jarmtin sẽ đi từ cổng vào (@) và đi đến lấy kim cương (x) và đi qua các vị trí trống (.) hoặc các vị trí có cọc (s). Các vị trí tường Jarmtin k thể đi (#). Sau khi lấy được kim cương Jarmtin sẽ thoát ra khỏi mê cung đúng vị trí (@). Nếu số lượng cọc Jarmtin đi qua cả đi lẫn về k vượt quá j (j là số lượng cọc Jarmtin có thể đi qua) thì in ra SUCCESS, nếu không hãy in ra IMPOSSIBLE.
Giải thuật: - Tìm ra vị trí của lối vào, gọi hàm backtrack với chiều vào. - tại mỗi ô tọa độ x, y hãy thử 4 ô xung quanh xem có thể đi hay không? nếu là vị trí trống thì đi tiếp, nếu là vị trí cọc hãy tăng số lượng cọc lên 1. nếu vượt quá số cọc cho phép thì thoát khỏi hàm. - Sử dụng 2 mảng visited cho 2 chiều vào và ra, sau khi đến được ô kim cương (x) thì gọi hàm backtrack với chiều ra. - Nếu chiều ra gặp được ô (@) tức là cách đi thỏa mãn, sử dụng cờ để thoát khỏi đệ quy. Chú ý: Bài này giải cho trường hợp tổng quá cổng vào và cổng ra nằm ở 2 tọa độ khác nhau. Còn với yêu cầu của bài này lối vào và lối ra là 1 ta chỉ cần tìm đường đi từ @ đến x với số lượng cọc đi qua là ít nhất và nhân 2 lần cho cả đường đi và về là xong :D Cho 1 bàn cờ sửa đổi được mô tả thành các hàng với vị trí cột bắt đầu và số lượng hình vuông trong hàng. Hãy tính số hình vuông ít nhất mà con mã không thể đi tới trong 1 lần nhảy liên tiếp. Vị trí bắt đầu của con mã sẽ là góc trên cùng bên trái. Giải thuật:
- 1 con mã có 8 vị trí đi, tại vị trí i, j hãy đi tiếp 1 trong 8 vị trí tiếp theo và đánh dấu những vị trí đã đi qua. - Sau khi đã thử ô con mã có thể đi hãy reset ô hiện tại và thử các trường hợp của các ô tiếp theo để được giá trị nhỏ nhất.
Bài này cho một ma trận 8x8 các số từ 1 đến 8 sẽ được xuất hiện duy nhất 1 lần trong hàng và cột. Trong 1 khối 4x4 các số từ 1 đến 8 xuất hiện k quá 2 lần. Nếu có tồn tại ma trận ứng với ma trận đầu vào hãy in ra "YES" và toàn bộ ma trận đó, nếu k tồn tại in ra "NO"
Giải thuật: - Kiểm tra ma trận đầu vào giá trị tại ô i,j xem đã tồn tại giá trị đó trong hàng, trong cột chưa.Tiếp tục kiểm tra xem nó có xuất hiện quá 2 lần tại ma trận con 4x4 chưa. Nếu 1 trong những điều kiện này không thõa mãn thì in ra "NO" và k cần sử dụng hàm backtrack. - Hàm backtrack cũng tương tự như bài EASY SUDOKU của bài trước, các bạn có thể tham khảo tại bài đó. Đề bài yêu cầu xác định ma trận sudoku dựa trên ma trận đầu vào 9x9. Với giá trị 0 là giá trị cần phải điền số phù hợp sao cho mỗi hàng, mỗi cột, mỗi hình vuông con 3x3 chỉ tồn tại duy nhất 1 số từ 1 đến 9. Nếu k thể tìm được ma trận phù hợp với đề bài in ra "No solution".
Cho ma trận kí tự MxN với kích thước k vượt quá 100x100. Hãy kiểm tra sự tồn tại của chuỗi “ALLIZZWELL” trong ma trận đó. Đường dẫn có thể được tìm thấy theo hàng ngang, dọc và đường chéo.
Giải thuật: Sử dụng Backtrack không nhớ để kiểm tra sự tồn tại của chuỗi. Hàm backtrack sẽ truyền vào số kí tự đã được tìm thấy của chuỗi “ALLIZZWELL” để lựa chọn kí tự tiếp theo. Ví dụ ban đầu count = 0 thì sẽ tìm kí tự 'A', khi tìm thấy A count sẽ tăng lên 1 để tìm kiếm kí tự 'L' và tiếp tục đến khi tìm được chuỗi. Sau khi tìm thấy thì ta sẽ dùng 1 cờ (flag) để thoát nhanh khỏi hàm đê quy. Bài toán yêu cầu tìm chiều dài của chuỗi kí tự liên tiếp bắt đầu từ 'A' dài nhất theo chiều dọc, ngang và đường chéo. Ma trận đầu vào kích thước không vượt quá 50x50 Giả sử cho ma trận 4x3 như hình dưới, thì chiều dài chuỗi kí tự liên tiếp sẽ là 4 như hình bên phải Giải thuật:
Sử dụng backtrack (Dựa trên DFS) trong đó sẽ lưu lại giá trị của chuỗi dài nhất kèm theo đánh dấu kí tự đã đi qua. |
Thời Gian
December 2021
Chủ ĐỀ
All
|