Breadth First Search (BFS)

C++

C++

• push: insertion at the back of the queue
• pop: deletion from the front of the queue
• front: which retrieves the element at the front without removing it.

1queue<int> q;
2q.push(1); // [1]
3q.push(3); // [3, 1]
4q.push(4); // [4, 3, 1]
5q.pop(); // [4, 3]
6cout << q.front() << endl; // 3

Java

Java

• add: insertion at the back of the queue
• poll: deletion from the front of the queue
• peek: which retrieves the element at the front without removing it

Java doesn't actually have a Queue class; it's only an interface. The most commonly used implementation is the LinkedList, declared as follows:

1Queue<Integer> q = new LinkedList<Integer>();
2q.add(1); // [1]
3q.add(3); // [3, 1]
4q.add(4); // [4, 3, 1]
5q.poll(); // [4, 3]
6System.out.println(q.peek()); // 3

C++

C++

The four methods for adding and removing are push_back, pop_back, push_front, and pop_front.

1deque<int> d;
2d.push_front(3); // [3]
3d.push_front(4); // [4, 3]
4d.push_back(7); // [4, 3, 7]
5d.pop_front(); // [3, 7]
6d.push_front(1); // [1, 3, 7]
7d.pop_back(); // [1, 3]

You can also access deques in constant time like an array in constant time with the [] operator. For example, to access the element $\text{i}$ for some deque $\text{dq}$, do $\text{dq[i]}$.

Java

Java

In Java, the deque class is called ArrayDeque. The four methods for adding and removing are addFirst , removeFirst, addLast, and removeLast.

1ArrayDeque<Integer> deque = new ArrayDeque<Integer>();
2deque.addFirst(3); // [3]
3deque.addFirst(4); // [4, 3]
4deque.addLast(7); // [4, 3, 7]
5deque.removeFirst(); // [3, 7]
6deque.addFirst(1); // [1, 3, 7]
7deque.removeLast(); // [1, 3]

C++

1int n,m, dist[MX], pre[MX];
2vi adj[MX];
3 
4int main() {
5    setIO(); re(n,m);
6    F0R(i,m) {
7        int a,b; re(a,b);
8        adj[a].pb(b), adj[b].pb(a);
9    }
10    FOR(i,2,n+1) dist[i] = MOD;

C++

1#include <bits/stdc++.h>
2using namespace std;
3
4int dx[4]{1, -1, 0, 0}, dy[4]{0, 0, 1, -1};
5
6int n, m, depth[4000][4000], ans = 1;
7string snow[4000];
8
9bool inside(int x, int y) {
10    return (x > -1 && x < n && y > -1 && y < m && snow[x][y] != '.');