Nhờ xem giúp thuật toán kiểm tra phần tử hoàng hậu trong ma trận

tcm · October 9, 2022, 12:09am

Hi mọi người. Em có code giải 1 bài tập sau nhưng do bài này tương đối không dễ nên sợ code của em có thể sai hoặc không đúng hết mọi trường hợp, nhờ mọi người xem xét giùm !

Đề bài: Kiểm tra 1 phần tử trong ma trận có phải là phần tử hoàng hậu hay không ? ( Định nghĩa: 1 phần tử được gọi là hoàng hậu khi nó lớn nhất trên dòng, cột và 2 đường chéo đi qua nó )

Source code: http://codepad.org/K57iMRpk

bool KiemTraHoangHau(int a[][MAX], int dong, int cot, int xdong, int xcot)
{
	for (int i = 0; i < dong; i++) // kiểm tra trên toàn cột đó
	{
		if (a[i][xcot] != a[xdong][xcot] && a[i][xcot] >= a[xdong][xcot])
			return false;
	}
	for (int j = 0; j < cot; j++) // kiểm tra trên toàn dòng đó
	{
		if (a[xdong][j] != a[xdong][xcot] && a[xdong][j] >= a[xdong][xcot])
			return false;
	}
	int vardong, varcot, vardong1, varcot1, vardong2, varcot2, vardong3, varcot3;
	vardong = vardong1 = vardong2 = vardong3 = xdong;
	varcot = varcot1 = varcot2 = varcot3 = xcot;
	for (;;) // kiểm tra đường chéo ở trên bên phải
	{
		vardong--;
		varcot--;
		if (vardong < 0 || varcot < 0)
			break;
		if (a[vardong][varcot] >= a[xdong][xcot])
			return false;
	}
	for (;;) // kiểm tra đường chéo ở dưới bên trái
	{
		vardong1++;
		varcot1++;
		if (vardong1 > dong - 1 || varcot1 > cot - 1)
			break;
		if (a[vardong1][varcot1] >= a[xdong][xcot])
			return false;
	}
	for (;;) // kiểm tra ở dưới đường chéo bên phải
	{
		vardong2++;
		varcot2--;
		if (vardong2 > dong - 1 || varcot2 < 0)
			break;
		if (a[vardong2][varcot2] >= a[xdong][xcot])
			return false;
	}
	for (;;) // kiểm tra ở trên đường chéo bên trái
	{
		vardong3--;
		varcot3++;
		if (vardong3 < 0 || varcot3 > cot - 1)
			break;
		if (a[vardong3][varcot3] >= a[xdong][xcot])
			return false;
	}
	return true;
}

Về vấn đề thuật toán của code em thì cũng đơn giản: Duyệt qua hết dòng, cột đang chứa nó và kiểm tra. Sau đó duyệt về đường chéo ở trên bên trái về dưới bên phải và kiểm tra. Cuối cùng là duyệt đường chéo ở trên bên phải về đường chéo ở dưới bên trái và kiểm tra. Nếu vẫn không có gì xảy ra thì lập tức kết luận phần tử đó là hoàng hậu.

Mọi người xem giúp em coi thuật toán có đúng, có chạy hết mọi trường hợp chưa? Có tối ưu chưa, nếu chưa thì cho em xin ý kiến thêm ! ( Lưu ý là ưu tiên cho đúng trước rồi mới tới tối ưu )

Xin cảm ơn mọi người nhiều

htwap · August 16, 2016, 1:47pm

mình nghĩ là kiểm tra trên dòng và cột thì nên sửa thế này:
a[i][xcot] != a[xdong][xcot] thành i != xdong
a[xdong][j] != a[xdong][xcot] thành j != xcot

Gio · August 16, 2016, 2:03pm

Tối ưu thêm một chút thì có thể tìm trước giá trị lớn nhất của max dong[0…n-1],cot[0…n-1], cheo_chinh[-n+1…n-1],cheo_phu[0…2n-2]. Khi đó hàm kiểm tra chỉ cần:

bool kiem_tra(int **matrix,int i,int j){
    int cur=matrix[i][j];
    return cur==cot[j] and cur==dong[i] and cur==cheo_chinh[i-j] and cur==cheo_phu[i+j];
}

tcm · August 16, 2016, 2:06pm

Vậy tức là code em đúng rồi hả anh ?
Mà anh giải thích sâu + rõ hơn tí được không chứ em hỏi khó hiểu

Gio · August 16, 2016, 2:16pm

Ở code của bạn mỗi phần tử cần kiểm tra 1 vòng for o(n) để so sánh,nhân với n*n số phần tử trên mảng như vậy mất n^3 phép toán.

Ở đây có thể tối ưu hàm kiểm tra bằng cách tính trước max của từng dòng, cột, chéo rồi so sánh. Bước kiểm tra sẽ nhanh hơn.
Còn phần tìm max của dòng,cột,chéo cũng khá đơn giản: ví dụ cho cheo_phu

fill(cheo_phu,cheo_phu+2*n,INT_MIN);
for(int i=0;i<n;++i)
    for(int j=0;j<n;++j)
         if(matrix[i][j]>cheo_phu[i+j]) cheo_phu[i+j]=matrix[i][j];