Tìm một thuật toán hiệu quả cho một hoạt động ma trận

Question

Đây là một câu hỏi phỏng vấn:

Đối với một ma trận, chúng ta định nghĩa một hoạt động khi chúng ta thêm từ 1 tới một mục nhập, tất cả các mục xung quanh (lên, xuống, bên trái, bên phải) cũng sẽ được thêm vào bởi 1. Cho một ma trận dương, tìm một thuật toán để xác định xem ma trận có thể được xây dựng từ ma trận không bằng cách sử dụng thao tác này hay không.

Thuật toán hiệu quả để giải quyết câu hỏi là gì?

Điều tôi có thể nghĩ là sử dụng backtracking để thử mọi kết hợp có thể, tuy nhiên điều này chắc chắn không hiệu quả. Câu hỏi này giống như trò chơi Tắt đèn, nhưng nó không phải là 0/1 ở đây mà làm cho phức tạp hơn.

Cảm ơn.

Edit:

Ví dụ:

3 3 can be constructed from 0 0 -> 1 1 -> 2 2 -> 3 3 
1 2       0 0 1 0 1 1 1 2 

Answer 1

đại số tuyến tính?

Cell i,j is touched x<sub>ij</sub> times. 

n biến và phương trình. Giải quyết. O(n^6) theo phương pháp Gaussian, các phương thức nhanh hơn khác có thể tồn tại.

Ngoài ra, ma trận là đặc biệt để có thể làm cho nó nhanh hơn.

Answer 2

tôi đã tìm thấy một vài thứ (đối với ma trận 2x2), muốn chia sẻ chúng đầu tiên
-sum của tất cả các phần tử trong ma trận phải chia hết cho 3 (thì chỉ có thể).
-Chúng phải thể hiện một ma trận được đưa ra trong hình thức cho phép hoạt động bước

3 3 -> 2* 1 1 + 1* 1 1 
1 2  0 1   1 0 

sẽ có một số trường hợp mà điều này không thể được thực hiện ví dụ

5 3 ->2* 1 0 + 2* 1 1  = 4 2 
2 4  1 1   0 1  2 4 

5 3 - 4 2  = 1 1 (this is not allowed operation) 
2 4  2 4  0 0