UVA – 928 – Eternal Truths

• Problem Statement : UVA – 928 – Eternal Truths
• Difficulty :  Hard  – 236 DACU
• Type : constrained BFS.
• Description :
  • the main problem was to realize the differences between the normal BFS constrains and those of this problem
  • Here you are allowed to pass upon a certain cell many numbers of times with maximum of 3 times.
  • AND you may visit each cell only once ( which is the visit that will generate the shortest Path ) For each No of Jumps of the 1, 2 , 3 moves from the previous cell to the current one.
  • so if you are going to visit this cell with 2 Jumps, you are allowed to visit it if and only if it was not visisted before from a 2 Jumps move.
  • The fact that this soloution generates the shortest path is still inheriting it’s validity from the original BFS proof as we didn’t break the condition that we donot travel to a certain level of depth from the source , untill we finish the shorter level preceding it.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>

#define VALID(I, J, N, M) (I)>=0 && (J)>=0 && (I)<(N) && (J)<(M)
#define INF 1<<29
using namespace std;
typedef pair<int, int> Point;

int main() {
	int dx[]= {-1, 0, 0, 1};
	int dy[]= {0, -1, 1, 0};
	int T, N, M, i, j, sourceX, sourceY, endX, endY;
	int prevMoves = 0, curMoves=1, curX, curY, nextX, nextY;
	int delta, bad, JUMP;
	cin >> T;
	while (T--) {
		cin >> N >> M;
		char graph[N][M];
		int d[N][M][4];
		for (i = 0; i < N; i++)
			for (j = 0; j < M; j++) {
				cin >> graph[i][j];

				d[i][j][1]=d[i][j][2]=d[i][j][3] = INF;
				if(graph[i][j]=='S'){ sourceY=i; sourceX=j; }
				if(graph[i][j]=='E'){ endY=i; 	 endX=j;    }
			}

		queue< pair<Point, int> > que;
		d[sourceY][sourceX][0]= 0;
		que.push( pair<Point, int> (Point(sourceY, sourceX), 0));
		bool found = false;

		while(!que.empty() && !found){
			curY = que.front().first.first, curX=que.front().first.second;
			prevMoves = que.front().second, curMoves = prevMoves%3 +1;
			que.pop();

			for(delta=0; delta<4; delta++){
				nextY = curY + dy[delta]*curMoves, nextX =curX + dx[delta]*curMoves;
				if(VALID(nextY, nextX, N, M) && graph[nextY][nextX]!= '#' && d[nextY][nextX][curMoves]==INF){

					for(JUMP = 1, bad=false; JUMP<=curMoves; JUMP++)
						bad = bad || graph[curY + dy[delta]*JUMP][curX + dx[delta]*JUMP]=='#';
					if(bad)continue;

					d[nextY][nextX][curMoves]= d[curY][curX][prevMoves] +1;
					if(nextY==endY && nextX==endX) found=true;
					que.push( pair< Point, int> (Point(nextY, nextX), curMoves));
				}
			}
		}

		if(!found)
			cout << "NO" << endl;
		else
			cout << d[endY][endX][curMoves] << endl;

	}

	return 0;
}