Code:
1.
#include <iostream>
#include <queue>
using namespace std;
int graph[100][100];
int visited[100];
int N;
void BFS(int v)
{
queue<int> q;
int u = v;
2.
visited[v] = 1; #include <iostream>
[Link](v); #include <queue>
using namespace std;
while (true)
{ #define MAX 10
for (int w = 0; w < N; w++)
{ int R, C;
if (graph[u][w] == 1 && visited[w] == 0) int maze[MAX][MAX];
{ int visited[MAX][MAX];
[Link](w); int distanceMaze[MAX][MAX];
visited[w] = 1; int parentX[MAX][MAX];
} int parentY[MAX][MAX];
}
// Directions: Down, Up, Right, Left
if ([Link]()) int dx[4] = {1, -1, 0, 0};
return; int dy[4] = {0, 0, 1, -1};
u = [Link](); void printPath(int ex, int ey) {
[Link](); int pathX[MAX * MAX];
cout << u << " "; int pathY[MAX * MAX];
} int len = 0;
}
while (ex != -1 && ey != -1) {
int main() pathX[len] = ex;
{ pathY[len] = ey;
int E; len++;
cin >> N >> E;
int px = parentX[ex][ey];
for (int i = 0; i < E; i++) int py = parentY[ex][ey];
{ ex = px;
int u, v; ey = py;
cin >> u >> v; }
graph[u][v] = 1;
graph[v][u] = 1; cout << "Path: ";
} for (int i = len - 1; i >= 0; i--)
int start; cout << "(" << pathX[i] << "," << pathY[i] <<
cin >> start; ") ";
cout << endl;
BFS(start); }
return 0; void MazeBFS(int startX, int startY, int endX, int
} endY) {
// Initialize arrays cin >> maze[i][j];
for (int i = 0; i < MAX; i++)
for (int j = 0; j < MAX; j++) { int startX, startY, endX, endY;
visited[i][j] = 0; cin >> startX >> startY;
distanceMaze[i][j] = 0; cin >> endX >> endY;
parentX[i][j] = -1;
parentY[i][j] = -1; MazeBFS(startX, startY, endX, endY);
}
return 0;
queue<pair<int,int>> q; }
[Link]({startX, startY});
visited[startX][startY] = 1;
distanceMaze[startX][startY] = 0;
parentX[startX][startY] = -1;
parentY[startX][startY] = -1;
while (![Link]()) {
int x = [Link]().first;
int y = [Link]().second;
[Link]();
if (x == endX && y == endY) {
break;
}
3.#include <iostream>
for (int i = 0; i < 4; i++) { using namespace std;
int nx = x + dx[i];
int ny = y + dy[i]; #define MAX 100
if (nx >= 0 && nx < R && ny >= 0 && ny < int qx[MAX * MAX], qy[MAX * MAX];
C && int visited[MAX][MAX];
maze[nx][ny] == 0 && visited[nx][ny] int dist[MAX][MAX];
== 0) { int parentX[MAX][MAX], parentY[MAX][MAX];
visited[nx][ny] = 1;
distanceMaze[nx][ny] = int dx[8] = {2, 2, -2, -2, 1, -1, 1, -1};
distanceMaze[x][y] + 1; int dy[8] = {1, -1, 1, -1, 2, 2, -2, -2};
parentX[nx][ny] = x;
parentY[nx][ny] = y; int N;
[Link]({nx, ny});
} int isValid(int x, int y) {
} return (x >= 0 && y >= 0 && x < N && y < N);
} }
if (!visited[endX][endY]) void knightMinMoves(int sx, int sy, int dx1, int
cout << "No path exists." << endl; dy1) {
else { int front = 0, rear = 0;
cout << "Shortest path length: " <<
distanceMaze[endX][endY] << endl; for (int i = 0; i < N; i++)
printPath(endX, endY); for (int j = 0; j < N; j++)
} visited[i][j] = 0;
}
qx[rear] = sx;
int main() { qy[rear] = sy;
cin >> R >> C; rear++;
for (int i = 0; i < R; i++) visited[sx][sy] = 1;
for (int j = 0; j < C; j++)
dist[sx][sy] = 0; int main() {
parentX[sx][sy] = -1; int sx, sy, dx1, dy1;
parentY[sx][sy] = -1;
cin >> N;
while (front < rear) { cin >> sx >> sy;
int x = qx[front]; cin >> dx1 >> dy1;
int y = qy[front];
front++; knightMinMoves(sx, sy, dx1, dy1);
if (x == dx1 && y == dy1) return 0;
break; }
for (int i = 0; i < 8; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (isValid(nx, ny) && visited[nx][ny] == 0)
{
visited[nx][ny] = 1;
dist[nx][ny] = dist[x][y] + 1;
parentX[nx][ny] = x;
parentY[nx][ny] = y;
qx[rear] = nx;
qy[rear] = ny;
rear++;
}
}
}
cout << "Minimum moves: " << dist[dx1][dy1]
<< endl;
cout << "Path:" << endl;
int pathX[MAX * MAX], pathY[MAX * MAX];
int len = 0;
int x = dx1, y = dy1;
while (x != -1 && y != -1) {
pathX[len] = x;
pathY[len] = y;
len++;
int px = parentX[x][y];
int py = parentY[x][y];
x = px;
y = py;
}
for (int i = len - 1; i >= 0; i--) {
cout << "(" << pathX[i] << "," << pathY[i] <<
")";
if (i != 0) cout << " -> ";
}
cout << endl;
}