A simple Floating Action Button that shows an anchored Navigation View Installation Include the library in your build.gradle
In your pom.xml if you are using Maven
Usage
Full Source download
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. 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. |
Thời Gian
December 2021
Chủ ĐỀ
All
|