Hỏi một bài toán về hình vuông (ma trận n*n)

#1

Mọi người giúp em bài này với ạ, cho em xin ý tưởng

Cho một bảng vuông N*N biểu diễn bởi các số 0 và 1, hãy đếm các số 1 cô độc.
Định nghĩa : số một cô độc là số 1 mà các ô kề bên nó không tính đường chéo đều
mang giá trị là 0.

Dữ liệu vào : SQUARE.INP

  • Dòng đầu là số N chỉ kích thước bảng vuông (1<N<=1000).
  • N dòng sau mỗi dòng là N số 0,1 cách nhau ít nhất một khoảng trắng.

Dữ liệu ra: SQUARE.OUT
Một số nguyên duy nhất là số ô 1 đơn độc có trong bước.

Ví dụ
SQUARE.INP
3
1 0 1
0 0 1
0 0 0
SQUARE.OUT
1
Giải thích: số 1 đầu tiên là số 1 cô độc duy nhất.

#2

tìm hiểu cách tính tổng 8 ô xug quanh nhé :))

#3

Đó là cái vấn đề của em.

  • Nếu số đó nằm ngay góc, làm sao để bỏ qua các phần tử không nằm trong ma trận, cả góc trên bên trái và dưới bên phải?
  • Làm sao chừa bé ở giữa ra?
#4

cho nó cái biên có các giá trị = 0

#5

Đây là code check của em, buồn là kết quả ra chẳng giống cái đề

bool CheckAlone1(int A[][1000], int n, int i, int j) // Check if A[i][j] is a alone one
{
    int x = i - 1;
    int y = j - 1;
    if(x < 0){x++;}
    if(y < 0){y++;}

    for(x; x <= i + 1; x++){
            if(x > i + 1){continue;}
        for(y; y <= j + 1; y++){
            if(y > j + 1){continue;}
            if(x == i && y == j){continue;}
            if(A[i][j] == 1){
                return false;
                break;
            }
        }
    }
    return true;
}
#6

bạn tạo ma trận bắt đầu từ cột 1 dòng 1 thôi, còn dòng 0 cột 0 và bao viền thì bạn cho nó có giá trị 0 :smiley:

#7

Có ma trận vuông -> duyệt ma trận thì có i và j
arr[i][j] thì không nói rồi vì cái đó căn bản.

Nếu không xét đường chéo thì xét 4 cạnh thuộc i và j, nghĩa là i - 1; i + 1; j -1; j+1

Gợi ý thế thôi còn cách dùng i j sao cho ra kết quả đúng thì phải phụ thuộc nhiều điều kiện lắm. Ví dụ nếu a[i][j] nằm cuối mảng thì phải làm sao, nằm đầu mảng thì phải làm sao và nằm ở các cạnh trái phải trên dưới :-D.

1 Like
#8

Em cần duyệt luôn các ô xung quanh để làm một bài khác nữa: tính tổng các ô xung quanh.
Mà chẳng lẽ mỗi điều kiện phải dùng mỗi cái if hả anh.

#9

Để duyệt 1 Ô ở vị trị bất kì, em cần duyệt 8 ô xung quanh thì em phải cộng 1 cặp dx,dy cho tất cả 8 ô:
Như minh họa phía dưới thì dx,dy luôn không đổi/

(y-1,x-1) | (y-1,x) | (y-1,x+1)
(y,x-1) | (y,x)| (y,x+1)
(y+1,x-1) | (y+1,x)| (y+1,x+1)

Do đó ta có thể lưu:

const int dx[]={0,0,-1,1,-1,-1,1,1};
const int dy[]={1,-1,0,0,-1,1,-1,1};

như vậy em cần có cặp dx,dy tương ứng 8 ô xung quanh cần duyệt

for(int i=0;i<8;++i){
   x1=x+dx[i];
   y1=y+dy[i];
   // (y1,x1) là vị trí ô gần kề cần duyệt
}
1 Like
#10

Cho mình ké với? mình cũng đang giải hệ pt 3 ẩn đầy đủ theo định thức Cramer.
cũng giải theo matrix n*n và tìm nghiệm x,y,z nhưng chưa đc.:frowning:

#include <iostream>
using namespace std;
void main()
{
	float detA,Dx,Dy,Dz,a1,a2,a3,b1,b2,b3,c1,c2,c3,d1,d2,d3;
	cout<<"Nhap vao a1:"<<endl;
	cin>>"a1";
	cout<<"Nhap vao a2:"<<endl;
	cin>>"a2";
	cout<<"Nhap vao a3:"<<endl;
	cin>>"a3";
	cout<<"Nhap vao b1:"<<endl;
	cin>>"b1";
	cout<<"Nhap vao b2:"<<endl;
	cin>>"b2";
	cout<<"Nhap vao b3:"<<endl;
	cin>>"b3";
	cout<<"Nhap vao c1:"<<endl;
	cin>>"c1";
	cout<<"Nhap vao c2:"<<endl;
	cin>>"c2";
	cout<<"Nhap vao c3:"<<endl;
	cin>>"c3";
	cout<<"Nhap vao d1:"<<endl;
	cin>>"d1";
	cout<<"Nhap vao d2:"<<endl;
	cin>>"d2";
	cout<<"Nhap vao d3:"<<endl;
	cin>>"d3";
	detA=(a1*b2*c3+b1*c2+c1+a3+a2*b3)-(c1*b2*a3+b1*a2+a1+c2*b3+c3);
	Dx=(d1*b2*c3+b1*c2+c1+d2*b3+d3)-(c1*b2*d3+c2*b3+c3+b1*a2+d1);
	Dy=(a1*d2*c3+d1*c2+c1+a2*d3+a3)-(c1*d2*a3+c2*d3+c3+d1*a2+d1);
	Dz=(a1*b2*d3+b1*d2+d1+a2*b3+a3)-(d1*b2*a3+d2*b3+d3+b1*a2+a1);
	if (detA!=0)
	{
		cout<<"Nghiem cua phuong trinh la:"<<endl
			<<"x="<<Dx/detA<<endl
			<<"y="<<Dy/detA<<endl
			<<"z="<<Dz/detA<<endl;
	}
	else
		cout<<"Phuong trinh vo so nghiem or vo nghiem";
	system("pause");
}
1 Like
#11

Công thức tính định thức của bạn sai rồi.
Bạn nên viết 1 hàm cho matran 3x3

Det3x3 = a1b2c3+ a2b3c1+ a3b1c2
-( a3b2c1+ a1b3c2+a2b1c3)

Cách nhớ của mình là a b c không đổi,
Cộng xuôi 1,2,3
Trừ 3 2 1
Hệ số tăng dần nếu > 3-> 1

1 Like
#12

A không nói công thức duỵet các ô xung quanh nữa vì đã có người cho rồi.

e xem tấm hình dưới đây (chụp máy cùi nên ko rõ lắm :smiley: cố mườn tượng ra ha)
IMG20150123102350 by nguyen vinh thinh, on Flickr

Các vị trí a đánh số là các ô xung quanh muốn xét

** Nếu: arr[i][j] (gọi tắt là arr đi :smiley: ) ở giữa, nghĩa là các ô từ 1 - 8 tồn tại. Cái này đơn giản.
** Nếu arr ở góc trên bên trái, các ô 1 - 2 - 3 - 4 - 6 không tồn tại.
** Nếu arr ở góc trên bên phải, các ô 1 - 2 - 3 - 5 - 8 không tồn tại.
** Còn 2 góc còn lại thì e suy ra đi :smiley: a lười viết quá.

** Nếu arr ở cạnh trên thì 1 2 3 không tồn tại
** Ở cạnh dưới thì 6 7 8 không tồn tại
** Cạnh phải thì 3 5 7 không tồn tại
** Cạnh trái thì 1 4 6 không tồn tại

Vậy qua 1 bài toán có rất nhiều vấn đề xảy ra. Nếu cứ áp dụng 1 phép tính tổng logic cho tất cả các trường hợp thì các trươnggf hợp trên sẽ bị báo lỗi khởi tạo hoặc báo lỗi runtime.Vì ví dụ arr ở góc trên bên trái thì arr[ i -1 ][ j - 1 ] đâu có tồn tại, vậy số đâu mà tính :smiley:

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?