Bài toán :
Đi từ các đỉnh X chứa giá trị 1 nằm trên hàng 0 có giá trị 1 xuống dưới đáy sao cho đi theo các giá trị 1 , gặp ngã rẽ bắt buộc phải rẽ khi nào đến hàng cuối cùng in ra vị trí x có chiều dài đến hàng cuối cùng mà có đường đi là đường ngắn nhất.
Nếu 2 vị trí có cùng giá của đường đi thì trả về vị trí cao nhất.
Ví dụ tại vị trí hàng 0 cột 4 đi mất 20, và hàng 0 cột 9 đi mất 20 thì in ra output là 9
Chú ý :
Input : Ma trận đầu vào là 100x100, chỉ có 2 giá trị là 0, 1.
Output : In ra cột có đường đi ngắn nhất và cao nhất.
Tải Input và đáp án tại đây.
Đi từ các đỉnh X chứa giá trị 1 nằm trên hàng 0 có giá trị 1 xuống dưới đáy sao cho đi theo các giá trị 1 , gặp ngã rẽ bắt buộc phải rẽ khi nào đến hàng cuối cùng in ra vị trí x có chiều dài đến hàng cuối cùng mà có đường đi là đường ngắn nhất.
Nếu 2 vị trí có cùng giá của đường đi thì trả về vị trí cao nhất.
Ví dụ tại vị trí hàng 0 cột 4 đi mất 20, và hàng 0 cột 9 đi mất 20 thì in ra output là 9
Chú ý :
Input : Ma trận đầu vào là 100x100, chỉ có 2 giá trị là 0, 1.
Output : In ra cột có đường đi ngắn nhất và cao nhất.
Tải Input và đáp án tại đây.
Giải thuật:
- Lưu đầu vào mảng 2 chiều.
- Nhiệm vụ đầu tiên là đánh dấu các vị trí số 1 tại hàng 0 (có thể xét lúc nhập đầu vào để giảm thời gian).
- Tại vị trí có giá trị 1 sẽ có 3 hướng đi là trái (0, -1), phải (0,1), xuống dưới (1, 0), đề bài yêu cầu gặp ngã rẽ là luôn luôn rẽ cho đến khi xuống cuối cùng, vì vậy chúng ta sẽ kiểm tra bên trái và bên phải sau đó đến phía dưới, mỗi lần tìm được thì tăng biến đếm đến khi chỉ số hàng là n - 1.
- Bài toán có thể giải bằng vòng lặp while giả xử điểm đang xét có chỉ số hàng là x, chỉ số cột là y và cách đi tiếp theo là 1 trong 3 hướng bên trên. Ví dụ hướng tiếp theo là xuống dưới thì điểm đang xét sẽ được cập nhật tọa độ là x+1, y. Cứ làm thế đến khi chỉ số hàng là n-1.
- Có thể giải bằng đệ quy, ở đây dùng DFS tức là khi đi qua 1 điểm thì đánh dấu đã đi qua và gọi đệ quy của điểm tiếp theo đến khi chỉ số hàng là n-1.
- Lưu đầu vào mảng 2 chiều.
- Nhiệm vụ đầu tiên là đánh dấu các vị trí số 1 tại hàng 0 (có thể xét lúc nhập đầu vào để giảm thời gian).
- Tại vị trí có giá trị 1 sẽ có 3 hướng đi là trái (0, -1), phải (0,1), xuống dưới (1, 0), đề bài yêu cầu gặp ngã rẽ là luôn luôn rẽ cho đến khi xuống cuối cùng, vì vậy chúng ta sẽ kiểm tra bên trái và bên phải sau đó đến phía dưới, mỗi lần tìm được thì tăng biến đếm đến khi chỉ số hàng là n - 1.
- Bài toán có thể giải bằng vòng lặp while giả xử điểm đang xét có chỉ số hàng là x, chỉ số cột là y và cách đi tiếp theo là 1 trong 3 hướng bên trên. Ví dụ hướng tiếp theo là xuống dưới thì điểm đang xét sẽ được cập nhật tọa độ là x+1, y. Cứ làm thế đến khi chỉ số hàng là n-1.
- Có thể giải bằng đệ quy, ở đây dùng DFS tức là khi đi qua 1 điểm thì đánh dấu đã đi qua và gọi đệ quy của điểm tiếp theo đến khi chỉ số hàng là n-1.