CSES - Labyrinth

Authors: Nathan Wang, Sofia Yang

Edit This Page

In this problem, we're asked to find and output the shortest path between two nodes. We can't use DFS here because we're looking for the shortest path. Instead, we can use BFS to solve this problem.

Below is a video solution for this problem by Jonathan Paulson. The video uses Python.

(Note: The video solution TLE's on one of the test cases. I think (??) it may be possible to get AC by setting SEEN[rr][cc] to true after line 42, and removing lines 23, 24, and 38. However, I haven't tested this.)

Implementation

C++

#include <bits/stdc++.h>


using namespace std;


#define ii pair<int, int>
#define f first
#define s second
#define mp make_pair


int n, m;

Java

import java.io.*;
import java.util.*;


public class cses1193 {
	public static int[] dX = {-1, 0, 0, 1};
	public static int[] dY = {0, -1, 1, 0};
	public static String dirs = "ULRD";


	// Coordinates for points A and B.
	public static point A = new point(-1, -1);

Python

from collections import deque


MAX_N = 1000
STEP_DIR = "URDL"


# 0 = up, 1 = right, 2 = down, 3 = left
DX = [-1, 0, 1, 0]
DY = [0, 1, 0, -1]


vis = [[False for _ in range(MAX_N)] for _ in range(MAX_N)]

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum