[C++]Thuật toán cờ caro ma trận nxm

Trò chơi cờ Ca rô là một trò chơi trí tuệ được biểu diễn trên một ma trận A có kích thước n*m ô, với n và m là số hàng và số cột của ma trận, lần lượt. Trên ma trận này, hai người chơi (thường là người X và người O) sẽ thay phiên nhau đánh dấu vào các ô trống. Dưới đây là bài viết giới thiệu thuật toán cờ caro trong ngôn ngữ lập trình c/c++

Bài trước: Bài 21:  tìm dòng có tổng lớn nhất trong ma trận

1. Bài toán cờ caro ma trận mxn

Bài 22 (TH-CSLT-04): Trò chơi cờ Ca rô được biểu diễn trên một Ma trận A n*m ô ( 0 < n, m < 51), trong đó:
Trò chơi kết thúc khi một người X hoặc O đạt được 5 ô liên tiếp giống nhau theo chiều ngang, chiều dọc hoặc đường chéo. Trạng thái hòa là trạng thái mà kết thúc toàn bộ bàn cờ mà không có người thắng cuộc.
Yêu cầu:
– Input: Cho ma trận thể hiện kết quả của cuộc thi đấu cờ Caro
– Output: Trạng thái của ván đấu. (X thắng; O thắng; Hòa; Trận đấu chưa kết thúc)

2. Thuật toán cờ caro c++

2.1 Trường hợp thắng theo hàng ngang/ cột dọc

Duyệt lần lượt các phần tử của mảng 2 chiều theo hàng ngang, cột dọc. Nếu phần tử giống với ký tự truyền vào thì tăng biến đếm.  Mỗi lần tăng, kiểm tra biến nếu bằng 5 thì trả về true ngược lại gán dem=0.

2.2 Kiểm tra đường chéo

Thuật toán:

//3. Kiem tra duong cheo
   for(int k=0;k<2*n-1;k++){
       dem=0;
       for(int i=0;i<n;i++){
           int j=k-i;
           if(j>=0 && j<m && a[i][j]==ch){
               dem++;
               if(dem==5) return true;
           }else{
               dem=0;
           }
       }
   }

Mô tả thuật toán: qua kết quả bàn cờ 6×5

+Với k=0

i=0;j=0; a[0][0]=x; dem=1

i=1;j=-1 nhỏ hơn 0; dem=0;

i=2;j=-2 nhỏ hơn 0; dem=0;

i=3;j=-3 nhỏ hơn 0; dem=0

i=4;j=-4 nhỏ hơn 0; dem=0

+Với k=1;

i=0;j=1; a[0][1]=x; dem=1;

i=1;j=1; a[1][0]=x; dem=2;

i=2;j=-1; nhỏ hơn 0; dem=0

i=3;j=-2; nhỏ hơn 0; dem=0

i=4;j=-3; nhỏ hơn 0; dem=0

+Với k=2

i=0;j=2; a[0][2]=o; dem=0;

i=1;j=1; a[1][1]=x; dem=1;

i=2;j=0; a[2][0]=x; dem=2;

i=3;j=-1; nhỏ hơn 0; dem=0

i=4;j=-2; nhỏ hơn 0; dem=0

+Với k=3

i=0;j=3; a[0][3]=o; dem=0;

i=1;j=1; a[1][1]=x; dem=1;

i=2;j=0; a[2][0]=x; dem=2;

i=3;j=-1; nhỏ hơn 0; dem=0

i=4;j=-2; nhỏ hơn 0; dem=0

+Với k=4

i=0;j=4; a[0][4]=x; dem=1;

i=1;j=3; a[1][3]=x; dem=2;

i=2;j=2; a[2][2]=x; dem=3;

i=3;j=1; a[3][1]=x; dem=4;

i=4;j=0; a[4][0]=x; dem=5; xuất ra màn hình x thắng

3. Code

#include<iostream>
#include<iomanip>

using namespace std;

const int n = 51;
const int m = 51;
char a[n][m];

bool checkWin(char ch){

    //1. kiem tra cot
    for(int i=0;i<n;i++){
        int count = 0;
        for(int j=0;j<m;j++){
            if(a[i][j]==ch){
                count++;
                if(count==5) return true;
            }else{
                count=0;
            }
        }
    }

    //2. kiem tra hang
    for(int j=0;j<m;j++){
        int count = 0;
        for(int i=0;i<n;i++){
            if(a[i][j]==ch){
                count++;
                if(count==5) return true;
            }else{
                count=0;
            }
        }
    }

    //3. kiem tra duong cheo
    for(int k=0;k<2*n-1;k++){
        int count = 0;

        for(int i=0;i<n;i++){
            int j=k-i;
            if(j>=0 && j<m && a[i][j]==ch){
                count++;
                if(count==5) return true;
            }else{
                count=0;
            }
        }
    }

    return false;

}

int main(){

    int n,m;
    cout<<"Nhap so hang: "; cin>>n;
    cout<<"Nhap so cot: "; cin>>m;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout<<"a["<<i<<"]["<<j<<"]: ";
            cin >> a[i][j];
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout<<setw(5)<<a[i][j];
        }
        cout<<endl;
    }

    if (checkWin('x')) {
        cout << "X thang" << endl;
        return 0;
    }


    if (checkWin('o')) {
        cout << "O thang" << endl;
        return 0;
    }

    cout << "Hoa. Tran dau chua ket thuc" << endl;
    return 0;

}

4. Kết quả

Trên đây là đoạn mã về thuật toán cờ caro được code bằng ngôn ngữ lập trình c++. Cảm ơn các bạn đã theo dõi trên ttnguyen.net.

Tải full bài tập thực hành lập trình C/C++ có lời giải:

Bài tiếp theo: Bài 23: sắp xếp mảng 2 chiều c++