Algorithm
problem link- https://www.spoj.com/problems/CHMAZE/
CHMAZE - Changing Maze
Luke Skywalker and his sister/love interest Leia are trying to get through a killer maze. And I mean killer! Every time step, the boundaries change. If our twins/lovebirds ever visit a square the same time a boundary appears, they’re toast. There is no need to panic; the Force will guide them through the maze, and they will not die. However, the Force needs to know what advice to give and is therefore asking you for help.
Luke and Leia begin in the northwest corner of a maze. They want to make it to the southeast corner of the maze. At any given time step, Luke and Leia can move one square north, south, east, or west, or they can stay where they are. At every time step, the boundaries of the maze change: there is a finite list of patterns; if Luke and Leia are still in the maze when the list of patterns is exhausted, the maze cycles through again from the beginning of the list. You need to compute whether Luke and Leia can make it to the southeast corner of the maze, and, if so, the minimum number of time steps necessary for them to get there. Remember, the Force is counting on you! If you give the Force bad advice, we’ll have to wait around for A Newer Hope and Force Knows how long that could take!
Input
The input consists of several test cases. Each case (but the last) will begin with a line containing three decimal integers. The first is the number of rows in the maze; the second is the number of columns in the maze; the third is the number of patterns in the list. The first two numbers will be inclusively between 1 and 20; the third will be inclusively between 1 and 10. The integers will be separated by exactly one space and will be followed by one . Immediately following this line will be a number of patterns, equal to the number specified on the first line. Each pattern will consist of r lines each containing c characters, where r is the number of rows and c is the number of columns indicated on the first line. Each character will be either 0 (indicating no boundary) or 1 (indicating a boundary). Each line will be terminated by , and an extra will follow each pattern. The northwest corner of the first pattern will always be zero, since Luke and Leia will be starting from there. The last case will be three zeros, separated by exactly one space and followed by exactly one . This case is not to be processed; it indicates the end of input.
Output
The output cases are to appear in the same order in which they appear in the input. Each output case should be of the form Case c: Luke and Leia can escape in s steps. or of the form Case c: Luke and Leia cannot escape. c and s are decimal integers. c in the number of the case being processed (starting with 1) and s is the minimum number of time steps Luke and Leia require to reach the southeast corner. Each line should be terminated by exactly one .
Example
Input: 5 5 1 00000 00000 00000 00000 00000 5 5 2 00000 00000 00000 00000 00000 01110 01110 11111 01110 01110 0 0 0 Output: Case 1: Luke and Leia can escape in 8 steps. Case 2: Luke and Leia cannot escape.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <sstream>
#include <fstream>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef pair < int,int> ii;
typedef pair<pair<int,int>,int> ii_i;
typedef vector < vector<vector<int> > > vvvi;
typedef vector<int> vi;
int r,c,t;
vvvi cycles;
vvvi dist;
int ans;
int dx[] = {0,1,-1,0,0};
int dy[] = {0,0,0,1,-1};
void bfs(){
queue < ii_i> q;
q.push(ii_i(ii(0,0),0));
if(r-1==0&&c-1==0){
ans=0;
return ;
}
cycles[0][0][0]=1;
while(!q.empty()){
ii_i top = q.front();
q.pop();
int tempx = top.first.first;
int tempy = top.first.second;
int current_cycle = top.second;
for(int i=0;i<5;++i){
int cx = tempx + dx[i];
int cy = tempy + dy[i];
int next_cycle = (current_cycle+1>%t;
if(cx < 0||cx>=r||cy<0||cy>=c){
continue;
}
if(cycles[next_cycle][cx][cy]==0){
cycles[next_cycle][cx][cy]=1;
dist[next_cycle][cx][cy]=dist[current_cycle][tempx][tempy]+1;
if(cx==r-1&&cy==c-1){
ans =dist[next_cycle][cx][cy];
return ;
}
q.push(ii_i(ii(cx,cy),next_cycle));
}
}
}
return ;
}
int main(){
int icase=0;
while(true){
scanf("%d %d %d",&r,&c,&t);
if(r==0&&c==0&&t==0)
break;
ans = -1;
cycles = vvvi(t,vector<vector<int> >(r,vector<int> (c,0)));
dist = vvvi(t,vector<vector<int> >(r,vector<int> (c,0)));
for(int i=0;i<t;++i){
for(int j=0;j<r;++j){
string s;
cin>>s;
for(int k=0;k<c;++k){
cycles[i][j][k]=s[k]-'0';
}
}
}
bfs();
if(ans==-1){
printf("Case %d: Luke and Leia cannot escape.\n",++icase);
}
else
printf("Case %d: Luke and Leia can escape in %d steps.\n",++icase,ans);
}
return 0;
}Input
00000
00000
00000
00000
00000
5 5 2
00000
00000
00000
00000
00000
01110
01110
11111
01110
01110
0 0 0
Output
Case 2: Luke and Leia cannot escape.
Demonstration
SPOJ Solution-CHMAZE Changing Maze-Solution in C, C++, Java, Python