- 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.
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. Cho 1 ma trận mxn. Mỗi ô trong ma trận chứa một giá trị k biểu thị số ô vuông mà nó có thể nhảy tới theo 4 hướng. Hãy xác định số lần di chuyển tối thiểu theo yêu cầu của đề bài để nhảy từ vị trí trên cùng bên trái xuống ô dưới cùng bên phải.
Giải thuật: Tại ô i,j lưu 4 hướng ứng với giá trị k nó có thể nhảy tới. nếu k = 0 k cần phải xét. Tiếp tục BFS đến khi gặp ô dưới cùng bên phải. Mảng visit sẽ lưu giá trị số bước đi. Mình lười viết Queue nên sử dụng luôn queue của C++ Cho một mê cung được mô tả bởi "#" là đá và "." là ô trống. Hãy tìm khoảng cách xa nhất giữa 2 ô trống.
Giải thuật: Dùng DFS hoặc BFS, sử dụng giải thuật DFS hoặc BFS tại 2 điểm bất kì sau đó DFS hoăc BFS tại điểm xa nhất của lần gọi hàm đầu tiên. Bài này mình ngại cài Queue các bạn tham khảo Queue ví dụ trước. Đàn mèo đang được thả rông trong thành phố, người ta chia thành phố thành các hình vuông nhỏ và biết rằng khi đi qua hình vuông đó con mèo sẽ đi tiếp một trong 4 hướng đông, tây, nam, bắc. Hãy in ra số lượng cạm bẫy ít nhất để bắt toàn bộ số mèo.
Giải thuật: Dùng BFS tại từng ô hãy thêm vào Queue những ô sau: - Giả sử đang tại ô i.j sẽ có 4 ô xung quanh là (i+1,j), (i-1, j), (i, j+1), (i, j-1), kiểm tra 4 ô này xem ô tiếp theo của nó có phải là ô i,j hay k? nếu có hãy đánh dấu đã visit và thêm vào Queue. - Tại ô i,j ta sẽ thêm ô tiếp theo của ô i,j vào Queue. ví dụ nếu đang ở ô i,j và i,j có giá trị 'S' (Hướng nam) thì hãy thêm ô tiếp theo là i+1, j vào Queue. Chú ý: Chỉ thêm những ô chưa được visit. Cho 1 thang máy với f là số lượng tầng của thang máy, s là tầng bắt đầu, g là tầng đích, u là số tầng mà thang đi khi nhấn nút "Up", d là số tầng mà thang đi khi ấn nút "Down".
Hãy in ra số lần bấm ít nhất nút "Up" hoặc "Down" để đi từ tầng s đến tầng g. Dùng BFS, tại tầng bắt đầu thêm 2 tầng tương ứng với nút up và down vào queue, tiếp tục làm vậy đến khi Queue rỗng, dùng mảng visited để đánh dấu và lưu trữ số lần bấm nút. Cho một mê cung, mê cung được làm bởi các cell và được kết nối với nhau bằng các đường 1 chiều. Người ta nhốt những con chuột vào trong mỗi cell và được đào tạo. Nhiệm vụ của bạn là in ra số lượng chuột thoát ra khỏi mê cùng trong thời gian T.
Giải thuật: Bài này là bài tìm đường đi ngắn nhất từ các cell đến lối ra. Các bạn có thể cài đặt BFS tại vị trí cổng thoát ra và đảo chiều đường đi để tìm thời gian tối thiểu đi từ lối ra đến các cell. Đến đây các bạn sẽ nghĩ rằng làm sao để cài đặt Dijsktra bằng BFS. Cũng giống như Dijisktra các bạn cũng define 1 mảng khoảng cách ngắn nhất từ đỉnh ban đầu đến các đỉnh còn lại là vô cùng Sau đó thay vì điều kiện của BFS bình thường là nếu chưa thăm thì đánh dấu đã thăm và không cho vào Queue nữa, thì BFS bằng Dijsktra sẽ luôn luôn kiểm tra các cell đã thăm, nếu tồn tại một khoảng cách tối ưu hơn sẽ cập nhật lại nó. Về cơ bản cài Dijsktra bằng BFS sẽ lâu hơn là cài thẳng Dijsktra vì vậy người ta có một khái niêm về hàng đợi ưu tiên (Priority Queue) để tăng tốc thuật toán này. Nếu muốn tìm hiểu search Wiki :D |
Thời Gian
December 2021
Chủ ĐỀ
All
|