Tìm đường đi để nhặt được nhiều đồng xu nhất

zhenande · February 19, 2016, 8:20pm

Cho ma trận mxn (m,n <=40), các giá trị trong ma trận từ 0->9, ngoại trừ điểm {0,0} và {n-1,m-1} có giá trị 1->9. Yêu cầu là đi từ {0,0} đến {n-1,m-1}. Chỉ đi được từ trái qua phải hoặc từ trên xuống, không được đi chéo và không được đi vào giá trị số 0. Phần Output cần chỉ ra số đồng xu tối đa lụm được và đường đi để lụm được số đồng xu đó. Nếu không thể đi được thì xuất ra thông báo ma trận không có lối ra.

#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <time.h>

using namespace std;

struct toaDo{
    int x;
    int y;
};

struct giaTri{
    int coin;
    int giaTriDuongDi;
    toaDo duongDiB[1000];
};

int a[50][50];
int n,m;
giaTri ketqua[1000];
int soCachDi=0;
toaDo duongDi[1000];
bool kiemtra=false;


void createData();
void inputData();
int tTry(int x,int y,int coin,int diaDiem);
void saveResult(int coin,toaDo duongDi[],int diaDiem);
void outputDuongDi(toaDo duongDiB[],int diaDiem);

int main()
{
    srand(time(NULL));
    createData();
    inputData();
    tTry(0,0,0,0);
    int maxi=0;
    for(int i=1;i<soCachDi;i++){
        if(ketqua[maxi].coin<ketqua[i].coin){
            maxi=i;
        }
    }
    if(!kiemtra){
        cout << "Ma Tran khong co loi ra.\n";
    }
    else{
        cout << "So coin lon nhat co the lum duoc la: " << ketqua[maxi].coin << endl;
        cout << "Duong di de co duoc so coin lon nhat la: ";
        outputDuongDi(ketqua[maxi].duongDiB,ketqua[maxi].giaTriDuongDi);
    }
    return 0;
}
//Lấy dữ liệu từ file txt
void inputData(){
    fstream f;
    f.open("InputData.txt",ios::in);
    if(!f.is_open()){
        cout << "File du lieu khong ton tai.";
        system("exit");
    }
    f >> n >> m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            f >> a[i][j];
        }
    }
    f.close();
}
//Thuật toán quay lui
int tTry(int x,int y,int coin,int diaDiem){
    bool flag=true;
    if(a[x][y+1] > 0){            //Nếu giá trị bên phải của nó >0 là có thể đi được
        coin+=a[x][y+1];
        duongDi[diaDiem].x=x;    //Lưu tọa độ điểm đang ở
        duongDi[diaDiem].y=y;
        diaDiem++;
        flag=false;                     
        tTry(x,y+1,coin,diaDiem);
    }
    if(a[x+1][y] > 0){
        if(!flag){               //Khi quay ngược lại thì coin cần phải trừ bớt do phần ở trên cộng thêm
            coin-=a[x][y+1];
            diaDiem--;
        }
        coin+=a[x+1][y];
        duongDi[diaDiem].x=x;
        duongDi[diaDiem].y=y;
        diaDiem++;
        tTry(x+1,y,coin,diaDiem);
    }
    if(x==(n-1) && y==(m-1)){          //Xét xem đi tới điểm ra ma trận
        coin+=(a[0][0]);
        saveResult(coin,duongDi,diaDiem);
    }
    return 0;
}
//Lưu lại đường đi để ra ma trận và số coin lụm được từ đường đi đó
void saveResult(int coin, toaDo duongDi[],int diaDiem){
    ketqua[soCachDi].coin = coin;
    ketqua[soCachDi].giaTriDuongDi = diaDiem;
    for(int i=0;i<diaDiem;i++){
        ketqua[soCachDi].duongDiB[i] = duongDi[i];
    }
    soCachDi++;
    kiemtra=true;
}
//Xuất ra đường đi
void outputDuongDi(toaDo duongDiB[],int diaDiem){
    for(int i=0;i<diaDiem;i++){
        cout << "{" << duongDiB[i].x << "," << duongDiB[i].y << "} -> ";
    }
    cout << endl;
}
//Tạo ma trận
void createData(){
    int x,y;
    x= rand()%40+1;
    y= rand()%40+1;
    fstream f;
    f.open("InputData.txt",ios::out);
    f << x << " " << y << endl;
    for(int i=0;i<x;i++){
        for(int j=0;j<y;j++){
            if((i==0 && j==0) || (i==x-1 && j==y-1)){
                f << rand()%9+1 << " ";
                continue;
            }
            f << rand()%10 << " ";
        }
        f << endl;
    }
    f.close();
    cout << "Ma tran da duoc tao ra va luu vao file InputData.txt\n";
}

Đây là code của mình. Hiện mình dùng thuật toán quay lui. Với ma trận nhỏ thì còn chạy ra chứ ma trận lớn là nó tắt thở rồi. Ai có cách nào khác giúp mình tối ưu nó hơn tý.

Nhờ sự hướng dẫn của @JuniorK mà mình đã tối ưu được bài này hơn, với thuật toán quay lui thì mình chỉ có thể tìm trong ma trận tầm <40, còn với cái này thì mình có thể tìm hơn đến 1000. Hiện tại ở các ma trận nhiều thì mình vẫn chưa kiểm tra hết được xem là có đúng hay không. Ở dưới mình sẽ post code của mình, mọi người có thể góp ý thêm giúp mình.

p/s: Mình không có search cái truy vết trên google. Mà nghĩ ra cái đó nên làm trước.

#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <time.h>

using namespace std;

struct toaDo
{
    int x;
    int y;
};

int a[1000][1000];
int sum[1000][1000];
int n,m;
int soCachDi=0;
toaDo duongDi[100000];
bool kiemtra=true;


void createData();
void inputData();
void quyHoachDong();
void truyVet();

int main()
{
    srand(time(NULL));
    createData();
    inputData();
    cout << "Bat dau giai ma tran.\n";
    quyHoachDong();
    cout << "Da giai xong ma tran.\n";
    return 0;
}

void inputData()
{
    cout << "Dang lay du lieu.....\n";
    fstream f;
    f.open("InputData.txt",ios::in);
    if(!f.is_open())
    {
        cout << "File du lieu khong ton tai.";
        system("exit");
    }
    f >> n >> m;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            f >> a[i][j];
        }
    }
    f.close();
    cout << "Da doc xong du lieu.\n";
}

void createData()
{
    int x,y;
    x= rand()%999+1;
    y= rand()%999+1;
    fstream f;
    f.open("InputData.txt",ios::out);
    f << x << " " << y << endl;
    for(int i=1; i<=x; i++)
    {
        for(int j=1; j<=y; j++)
        {
            if((i==1 && j==1) || (i==x && j==y))
            {
                f << rand()%9+1 << " ";
                continue;
            }
            f << rand()%10 << " ";
        }
        f << endl;
    }
    f.close();
    cout << "Ma tran da duoc tao ra va luu vao file InputData.txt\n";
}

void quyHoachDong()
{
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            if(i==1 && j==1){
                sum[i][j] = a[i][j];
            }
            else if(i==1){
                sum[i][j] = a[i][j] + sum[i][j-1];
            }
            else if(j==1){
                sum[i][j] = a[i][j] + sum[i-1][j];
            }
            else if(a[i][j-1]!=0 || a[i-1][j]!=0)
                sum[i][j] = a[i][j] + (sum[i-1][j] > sum[i][j-1] ? sum[i-1][j] : sum[i][j-1]);
        }
    }
    if(sum[n][m]==0){
        cout << "Ma tran khong co loi ra.\n";
    }
    else{
        cout << "So coin lon nhat co the nhan duoc la: " << sum[n][m] << endl;
        cout << "Duong di de co duoc so coin lon nhat: ";
        truyVet();
    }
}

void truyVet()
{
    int test;
    int i=n,j=m;
    while(i>1 || j>1)
    {
        test=sum[i][j] - a[i][j];
        if(test==sum[i-1][j])
        {
            duongDi[soCachDi].x=i;
            duongDi[soCachDi].y=j;
            soCachDi++;
            i--;
        }
        else
        {
            duongDi[soCachDi].x=i;
            duongDi[soCachDi].y=j;
            soCachDi++;
            j--;
        }
    }
    cout << "{1,1} -> ";
    for(i=soCachDi-1; i>0; i--)
    {
        cout << "{" << duongDi[i].x << "," << duongDi[i].y << "} -> ";
    }
    cout << "{" << duongDi[i].x << "," << duongDi[i].y << "}";
    cout << endl;
}

JuniorK · February 19, 2016, 7:44am

gọi a[i][j] là số coin tối đa mà nhặt được tại ô i,j ta có a[i][j]=max(a[i][j-1],a[i-1][j])+coin[i][j]
kết quả bài toán a[n-1][m-1], còn truy vết bạn tự tìm hiểu ahihi

zhenande · February 19, 2016, 11:33am

Hiện tại mình đang có thắc mắc là, làm sao để biết được rằng ma trận đó có lối ra hay không? Vì với việc tính tổng như thế thì nếu có +0 vào thì cũng không biết được.

for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            if(i==0 && j==0)
            {
                sum[i][j] = a[i][j];
            }
            else if(i==0)
            {
                if(a[i][j]==0){
                    if(a[i+1][j-1]==0){
                        kiemtra=false;
                    }
                    break;
                }
                sum[i][j] = a[i][j] + sum[i][j-1];
            }
            else if(j==0)
            {
                if(a[i][j]==0){
                    continue;
                }
                sum[i][j] = a[i][j] + sum[i-1][j];
            }
            else
            {
                if(a[i][j]==0){
                    if(a[i+1][j-1]==0){
                        kiemtra=false;
                    }
                    break;
                }
                sum[i][j] = a[i][j] + (sum[i-1][j] > sum[i][j-1] ? sum[i-1][j] : sum[i][j-1]);
            }
        }
        if(!kiemtra){
            break;
        }
    }
    if(!kiemtra){
        cout << "Ma tran khong co loi ra.\n";
    }
    else{
        cout << "So coin lon nhat co the nhan duoc la: " << sum[n-1][m-1] << endl;
        cout << "Duong di de co duoc so coin lon nhat: ";
        truyVet();
    }

Hiện tại với ma trận mình tự nghĩ ra thì cơ bản nó chạy được nhưng random thì vẫn chạy không ra ở 1 số ma trận có lối ra. ví dụ:

8 10
1 8 3 0 8 7 8 6 0 4
0 9 8 3 5 7 0 3 7 7
7 3 4 4 3 0 1 4 7 3
0 0 9 4 9 1 0 5 7 3
2 0 0 1 2 3 9 2 8 1
7 7 5 5 3 5 2 2 8 3
8 8 3 9 2 2 5 5 5 0
9 3 3 5 9 7 4 0 5 9

Với 2 con số 0 mình in đậm thì nó sẽ ngừng chương trình ở đó luôn. Còn nếu mình để nó không ngừng chỗ đó thì có 1 số trường hợp bị phí thời gian như 2 ô bên phải và dưới của ô vào ma trận đều là số 0. Thì nó có thể dừng tại đó luôn thay vì chạy tiếp. Vậy mình phải đặt điều kiện sao để nó có thể xử ly các trường hợp mà ma trận không có lối ra đây???

JuniorK · February 19, 2016, 12:23pm

ban đầu khởi tạo mảng là số âm đi nếu ô phía trên hay bên trái >0 thì mới xét cuối cùng ô n-1,m-1 >0 thì có đường đi, nên dùng mảng từ ô 1,1 để đỡ phải xét biên cho biên là 0 thôi

zhenande · February 19, 2016, 2:58pm

Cho việc tạo mảng số âm xong, còn việc dùng mảng từ ô 1,1 để khỏi xét biên thì cũng z, vì như bạn nói là nếu ô phía trên hay bên trái >0 nghĩa là với 1,1 thì khi ô trên nó chắc chắn mang giá trị âm, hoặc 1 giá trị rác nào đó, mình thì khai báo mảng toàn cục nên nó sẽ có giá trị 0 (mặc định trước khi cho thanh mảng âm) và với điều kiện đó nó sẽ không có giá trị sum cho hàng sum[1][m] và sum[n][1] => vẫn phải xét biên. Nếu không xét biên thì với ma trận MxN nó sẽ chỉ tính từ điểm 2,2 ( với việc dùng mảng từ ô 1,1 ) đến điểm ra của ma trận. Và với ma trận như thế này:

1 0 0 0 0
1 0 0 0 0
1 0 0 0 0
1 0 0 0 0
1 1 1 1 1

thì nó sẽ bị lỗi vì nó không tính được hàng 1 dọc bên trái. Vậy suy cho cùng là vẫn phải xét biên @@

Ta_Ta_Goo · February 19, 2016, 3:25pm

bàu này dùng quy hoạch động nhé thớt. lên google search làm cách làm bài triangle. làm xong cốt làm được bài này nhé. có gì ib mình.

anon10499953 · February 19, 2016, 4:08pm

Đây là thuật toán của mình, đề cũng tương tự với bạn: cho ma trận 9x9, mỗi ô chứa các giá trị 1, 2, 3, -1 tương ứng với nấm1, 2, 3 và nấm độc. Xuất phát từ (0, 0) đến (8, 8), chỉ đi xuống hoặc đi ngang và không được đi vào ô -1 và phải đi qua ít nhất 2 nấm khác loại:

bool CAPDlg::backTrack(int i, int j, int numberOfMushroom, int lastMushroom) {
	if (i == 8 && j == 8 && numberOfMushroom >= 2) {
		return true;
	}
	for (int turn = 0; turn < 2; turn++) {
		if (turn == 0 && i + 1 < 9 && array[i + 1][j] != -1) {
			if (lastMushroom != array[i + 1][j] && array[i][j + 1] != 0) {
				numberOfMushroom++;
			}
			lastMushroom = array[i + 1][j];
			if (backTrack(i + 1, j, numberOfMushroom, lastMushroom)) {
				cbitmapbegin.LoadBitmapW(IDB_BITMAP1);
				map[i + 1][j]->SetBitmap((HBITMAP)cbitmapbegin.Detach());
				return true;
			}
		}
		else if (turn == 1 && j + 1 < 9 && array[i][j + 1] != -1) {
			if (lastMushroom != array[i][j + 1] && array[i][j + 1] != 0) {
				numberOfMushroom++;
			}
			lastMushroom = array[i][j + 1];
			if (backTrack(i, j + 1, numberOfMushroom, lastMushroom)) {
				cbitmapbegin.LoadBitmapW(IDB_BITMAP1);
				map[i][j + 1]->SetBitmap((HBITMAP)cbitmapbegin.Detach());
				return true;
			}
		}
	}
	return false;
}

zhenande · February 19, 2016, 11:45pm

Cái này mình cũng chưa tìm hiểu do mới làm xong phần tìm đường đi trong ma trận, cái tự nghĩ nếu ma trận có số lớn hơn 1 thì tìm như thế nào để được nhiều điểm nhất thôi. @@

JuniorK · February 20, 2016, 5:18am

Truy vết là cả 1 nghệ thuật không đơn giản như bạn nghĩ đâu
nó hay ở chỗ khi mà ô bên trên và bên trái bằng nhau thì chọn cái nào?

zhenande · February 21, 2016, 12:27am

Tại mình nghĩ nếu trên hoặc trái mà cùng giá trị thì nó vẫn sẽ đưa về 1 đường cả. (Ở cái bài này là như thế) nên có thể đơn giản hơn tý như vậy ở bài này