Tìm đường đi trong mê cung - ma trận có kích thước 100x100

Tìm đường đi trong mê cung - ma trận có kích thước 100x100

Một mê cung được cho như hình bên dưới. Mê cung là một ma trận có kích thước 100x100. Trong đó màu trắng là đường đi, màu vàng là tường. Hãy tìm đường đi từ điểm bắt đầu có giá trị 2 đến điểm kết thúc có giá trị 3.

Giả sử đỉnh trên cùng bên trái có tọa độ là (0,0). Điểm bắt đầu là (1,1), điểm kết thúc là (13,13).

Hãy viết chương trình kiểm tra có thể đi từ điểm đầu đến điểm cuối. Nếu có đường đi in ra 1 ngược lại in ra 0.

bai toan me cung

[Input]

Dữ liệu đầu vào được ghi trong file MAZE.INP.

Dòng đầu ghi số thứ tự test case.

Các dòng tiếp theo là ma trận 100x100.

[Output]

Kết quả ghi ra file MAZE.OUT bắt đầu bằng ký tự #C theo sau là khoảng trắng, 0 nếu không có đường đi, 1 nếu có đường đi.

[I/O example]

7 10
1 1 1 0 0 1 0 0 1 1
1 1 1 0 1 0 0 0 0 0
1 1 0 0 0 1 1 1 0 1
1 1 0 1 0 1 1 1 0 1
1 1 0 0 0 0 0 1 0 0
1 1 0 1 0 1 0 0 0 0
1 1 0 0 0 0 0 1 1 1

[Output]

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

Chương trình cài đặt:

#include<iostream>

#include<conio.h>

#define nMax 100

using namespace std;

char matrix[nMax][nMax];

bool isReached;

void visit(char matrix[nMax][nMax], int x,int y){

 if(matrix[x][y] == '3'){

  isReached = true; return;

 }

 matrix[x][y] = '1';

 if(isReached == false && x-1 >=0 && (matrix[x-1][y] == '0' || matrix[x-1][y] == '3')) visit(matrix,x-1,y);

 if(isReached == false && x+1 <nMax && (matrix[x+1][y] == '0' || matrix[x+1][y] == '3')) visit(matrix,x+1,y);

 if(isReached == false && y-1 >=0 && (matrix[x][y-1] == '0' || matrix[x][y-1] == '3')) visit(matrix,x,y-1);

 if(isReached == false && y+1 <nMax && (matrix[x][y+1] == '0' || matrix[x][y+1] == '3')) visit(matrix,x,y+1);

}

int main(){

 freopen("MAZE.INP","r", stdin);

 freopen("MAZE.OUT","w", stdout);

 int testCase;

 int loop =1;

 int beginX, beginY;

 while(loop++ <= 10){

  isReached = false;

  cin>>testCase;

  for(int i=0;i<nMax;i++){

   cin>>matrix[i];

   for(int j=0;j<nMax;j++)

    if(matrix[j][i] == '2'){

     beginX = j; beginY = i;

   }

  }

  visit(matrix,beginX,beginY);

  if(isReached){

   cout<<"#"<<testCase<<" "<<1<<endl;

  }else{

   cout<<"#"<<testCase<<" "<<0<<endl;

  }

  

 }

 return 0;

}

 

Bạn thấy bài viết này như thế nào?: 
Average: 9 (8 votes)
Ảnh của Tommy Tran

Tommy Tran owner Express Magazine

Drupal Developer having 9+ year experience, implementation and having strong knowledge of technical specifications, workflow development. Ability to perform effectively and efficiently in team and individually. Always enthusiastic and interseted to study new technologies

  • Skype ID: tthanhthuy
  • Phone/Zalo: (+84) 944 225 212
  • WhatsApp: (+84) 944 225 212
  • Line Messenger: (+84) 944 225 212
  • Email: asaleotestf@gmail.com
  • Telegram Messenger: https:/t.me/tommytran0401

Quảng cáo việc làm

 

Thích hợp các bạn nữ mảng thợ may làm việc tại nước NGA

Đơn hàng Tuyển dụng 100 Thợ may đi Nga(đợt 1 tháng 3.2021, đợt 2 tháng 5.2021). Lương thực lãnh 800 USD, bao ăn ở, vé máy bay và visa, phí xuất cảnh(1800 USD)trả khi đi làm có lương. Bạn có thể liên hệ CÔNG TY qua Phone/Zalo: (+84) 944 225 212. Công ty sẽ tư vấn cho bạn.

Xem chi tiết: >>> https://bit.ly/3o9NOfR

Advertisement

 

jobsora

Dich vu khu trung tphcm

Dich vu diet chuot tphcm

Dich vu diet con trung

Quảng Cáo Bài Viết

 
Những phụ kiện công nghệ tuyệt nhất 2011

Những phụ kiện công nghệ tuyệt nhất 2011

Vòng tay theo dõi sức khỏe, tai nghe chống ồn, chuột cảm ứng,..những phụ kiện cực kì xinh xắn nhưng cũng không kém phần thông minh.

 Sony “bán tháo” liên doanh màn hình LCD với Samsung?

Sony “bán tháo” liên doanh màn hình LCD với Samsung?

Theo Nikkei, nhà sản xuất điện tử Nhật Bản đang gặp khó khăn với hoạt động kinh doanh TV bị thua lỗ.

Các cách để save a node in Drupal

Các cách để save a node in Drupal

Every day, millions of nodes are saved. It happens every time content is created, migrated, or updated. It's probably the most common content management task in Drupal.