Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- struct node { // Store two coordinates
- int row;
- int col;
- };
- int
- arr[100][100], // The input matrix
- n, m; // Matrix size
- node
- prev[100][100], // Store previous vertices
- knight[100]; // Store knights' coordinates
- bool
- visited[100][100], // Store visited vertices
- found; // Flag if Eli was found
- void dfs(int i, int j) { // Depth-first search
- if (found)
- return;
- if ( arr[i][j] == 'E' ) { // Eli was found
- found = true;
- return;
- }
- visited[i][j] = true;
- if ( !visited[i][j-1] && j-1 >= 0 && arr[i][j-1] != '#' ) { // Go left
- //printf("left\n");
- prev[i][j-1].row = i;
- prev[i][j-1].col = j;
- dfs(i, j-1);
- }
- if ( !visited[i][j+1] && j+1 < m && arr[i][j+1] != '#' ) { // Go right
- //printf("right\n");
- prev[i][j+1].row = i;
- prev[i][j+1].col = j;
- dfs(i, j+1);
- }
- if ( !visited[i+1][j] && i+1 < n && arr[i+1][j] != '#' ) { // Go down
- //printf("down\n");
- prev[i+1][j].row = i;
- prev[i+1][j].col = j;
- dfs(i+1, j);
- }
- if ( !visited[i-1][j] && i-1 >= 0 && arr[i-1][j] != '#' ) { // Go up
- //printf("up\n");
- prev[i-1][j].row = i;
- prev[i-1][j].col = j;
- dfs(i-1, j);
- }
- }
- int main() {
- node eli; // Store Eli's coordinates
- knight[0].row = 0; // Store number of knights
- int result = 0;
- char c;
- // Prepare input data
- scanf("%d %d", &n, &m);
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < m; j++) {
- scanf("%c", &c);
- if (c != '\n') {
- arr[i][j] = c;
- if (c == 'E') { // If it's Eli, save her coordinates
- eli.row = i;
- eli.col = j;
- }
- if (c == 'K') { // If it's a knight, save his coordinates
- knight[++(knight[0].row)].row = i;
- knight[knight[0].row].col = j;
- }
- } else { // If it's a new line
- j--;
- }
- }
- }
- // Sum knights' paths to Eli
- for (int i = 1; i <= knight[0].row; i++) {
- // Resets
- for (int j = 0; j < n; j++) {
- for (int k = 0; k < m; k++) {
- visited[j][k] = false;
- prev[j][k].row = prev[j][k].col = -1;
- }
- }
- found = false;
- // dfs the knight
- dfs(knight[i].row, knight[i].col);
- if (found) {
- node trace = eli;
- while (trace.row != -1 && trace.col != -1) {
- result++;
- trace = prev[trace.row][trace.col];
- }
- result--;
- }
- }
- if (result != 0)
- printf("%d\n", result);
- else
- printf("%d\n", -1);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement