[Bài toán] Tìm đường đi trong ma cung.

[Bài toán] 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.

[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]
Tải file input tại đây..
[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;
}

Cám ơn bạn đã đọc bài viết này. Hãy chia sẻ bài viết và bình luận ý kiến của bạn ở bên dưới.

Share this

Chào mừng bạn đến với SimpleCodeCJava Blog - Mục đích của chúng tôi khi thành lập blog này là muốn chia sẻ những kiến thức và kinh nghiệm lập trình mà chúng tôi đã học được với mong muốn giúp đỡ mọi người, giúp bạn rút ngắn được thời gian tìm hiểu cũng như việc giải quyết những vấn đề trong lập trình C và Java.