Is there a way to reach the final box - GRAPH

Question

There is a problem: The first person (who starts over) must reach the final box “e”, so that the second person “l” (whenever he is) could not catch the first person. Men can go left, right, up, down, or can stay.

For instance:

Input: 6 7 RRRRRRR R_e___R R_____R R_RRR_R R_gRl_R RRRRRRR 

The answer is "YES" because there is a way ("Left", "Up", "Up", "Up", "Right").

How can this problem be implemented?

I use BFS and DFS. Here is my code

 #include <iostream> #include <algorithm> #include <stack> #include <math.h> #include <cstring> #include <map> #include <queue> using namespace std; const int MAX = 32; char a[MAX][MAX]; int used[MAX][MAX], m1[MAX][MAX], m2[MAX][MAX];; int movesx[8] = {-1, 1, 0, 0}; int movesy[8] = { 0, 0, -1, 1}; int n, m, c = 0, flag = 0; struct pc { int x, y; }; pc li, ga, fi; queue <pc> q; void BFS1(pc v) { pc from, to; memset(m1,0,sizeof(m1)); m1[vy][vx] = 0; memset(used, 0, sizeof(used)); q.push(v); used[vy][vx] = 1; while(!q.empty()) { from = q.front(); q.pop(); for(int i = 0; i < 4; ++i) { int x = from.x + movesy[i], y = from.y + movesx[i]; if( (a[y][x] == ' ' || a[y][x] == 'g' ) && !used[y][x]) { used[y][x] = 1; m1[y][x] = m1[from.y][from.x] + 1; pc temp; temp.x = x; temp.y = y; q.push(temp); } } } } void BFS2(pc v) { pc from, to; memset(m2,0,sizeof(m2)); m2[vy][vx] = 0; memset(used, 0, sizeof(used)); q.push(v); used[vy][vx] = 1; while(!q.empty()) { from = q.front(); q.pop(); for(int i = 0; i < 4; ++i) { int y = from.y + movesy[i], x = from.x + movesx[i]; if( (a[y][x] == ' ' || a[y][x] == 'l' ) && !used[y][x]) { used[y][x] = 1; m2[y][x] = m2[from.y][from.x] + 1; pc temp; temp.x = x; temp.y = y; q.push(temp); } } } } void DFS(pc v) { used[vy][vx] = 1; for(int i = 0; i < 4; ++i) { int x = vx + movesx[i], y = vy + movesy[i]; if(a[y][x] == 'e') { c = 1; flag = 1; return; } if( (a[y][x] == ' ' ) && !used[y][x] && m2[y][x] < m1[y][x] && flag == 0 ) { pc temp; temp.x = x; temp.y = y; DFS(temp); } } } int main() { c = 0, flag = 0; memset(used, 0, sizeof(used)); memset(a, 'R', sizeof(a)); cin >> n >> m; string s; getline(cin, s); for(int i = 0; i < n; ++i) { getline(cin, s); for(int j = 0; j < m; ++j) { a[i][j] = s[j]; if(a[i][j] == 'g') { ga.x = j; ga.y = i; } else if(a[i][j] == 'l') { li.x = j; li.y = i; } else continue; } } BFS1(li); BFS2(ga); memset(used, 0, sizeof(used)); DFS(ga); if(c == 1) { cout << "YES" << endl; } else { cout << "NO" << endl; } } 

Here is the second code:

 #include <iostream> #include <algorithm> #include <stack> #include <math.h> #include <cstring> #include <map> #include <queue> using namespace std; const int MAX = 32; char a[MAX][MAX]; int used[MAX][MAX], m1[MAX][MAX], m2[MAX][MAX];; int an[1002][MAX][MAX]; int movesx[8] = {-1, 1, 0, 0, 0}; int movesy[8] = { 0, 0, -1, 1, 0}; int n, m, c = 0, flag = 0; struct pc { int x, y; }; pc li, ga; void functionD() { for(int z = 1; z <= 1000; ++z) { for(int i = 0; i < n; ++i) { for(int j = 0; j < n; ++j) { if(an[z - 1][i][j] == 1) { int x, y; for(int k = 0; k < 5; ++k) { x = j + movesx[k]; y = i + movesy[k]; if(x < m && y < n && x >= 0 && y >= 0) { if(a[y][x] != 'R' && a[y][x] != 'e') { an[z][y][x] = 1; } } } } } } } } void DFS(pc v, int k) { used[vy][vx] = 1; for(int i = 0; i < 5; ++i) { int x = vx + movesx[i], y = vy + movesy[i]; if(a[y][x] == 'e') { c = 1; flag = 1; return; } if(an[k][y][x] == 0 && a[y][x] != 'R' && !used[y][x] && flag == 0 && k <= 1000) { pc temp; temp.x = x; temp.y = y; DFS(temp, k + 1); } } } int main() { int nn; cin >> nn; for(int z = 0; z < nn; ++z) { c = 0, flag = 0; memset(used, 0, sizeof(used)); memset(a, 'R', sizeof(a)); cin >> n >> m; string s; getline(cin, s); for(int i = 0; i < n; ++i) { getline(cin, s); for(int j = 0; j < m; ++j) { a[i][j] = s[j]; if(a[i][j] == 'g') { ga.x = j; ga.y = i; } else if(a[i][j] == 'l') { li.x = j; li.y = i; } } } an[0][li.y][li.x] = 1; functionD(); DFS(ga, 1); if(c == 1) { cout << "YES" << endl; } else { cout << "NO" << endl; } } } 

EDIT (By Jarod42):

I found a complex map that failed:

 9 9 RRRRRRRRR R...Rg..R R.RlRRR.R RR..RR R.RRR.RR R.Re....R RRRRR.R R.......R RRRRRRRRR 

l cannot protect both accesses e .

or even easier

 RRRRRRRRRR R...RRRRRR RR..RRRR RlReR...gR RR..RRRR R...RRRRRR RRRRRRRRRR 

Answer 1

No need for DFS. Just check if l reach e to g . If he can, then he can catch g , otherwise g will win.

(And be careful with the redundant code in your code, BFS1 and BFS 2 are almost identical and can be combined into one function.)

EDIT: OP added (link to) new information: l cannot enter e .

The correction to this algorithm is obvious, if not elegant. Consider the rooms surrounding e ; if there is g can reach up to l , then g wins.

There may be other catches in the related task; The OP may state a problem that he wants to answer in the question itself. We do not like questions "links only."

Answer 2

You must first create a distance from each access to e .

Then this is minmax (or alpha beta):

• if g current position at one map distance is less than l current position is the same map distance, g wins.
• if l has a smaller or equal distance at all map distances, g loses.
• else g must use one of its valid cards to achieve the goal, counters l with its cards (or stands).

(Note: g has no reason to stand, because l can do the same, and we are at the same point).

(Edit: Note: in the provided link, it seems that the safe path should be chosen statically, so the dynamic part (3rd bullet) is free for g )