Tap here to switch tabs
Problem
Submissions

Problem: Paths in Maze That Lead to Same Room

Paths in Maze That Lead to Same Room counts the maze's confusion score: the number of distinct cycles using exactly three rooms, given an undirected corridor list.

Statement

A maze consists of nn rooms numbered from 1−n1 - n, and some rooms are connected by corridors. You are given a 2D integer array, corridors, where corridors[i]=[room1,room2]corridors[i] = [room1, room2] indicates that there is a corridor connecting room1room1 and room2room2, allowing a person in the maze to go from room1room1 to room2room2 and vice versa.

The designer of the maze wants to know how confusing the maze is. The confusion score of the maze is the number of different cycles of length 3.

For example, 1→2→3→11 → 2 → 3 → 1 is a cycle of length 33, but 1→2→3→41 → 2 → 3 → 4 and 1→2→3→2→11 → 2 → 3 → 2 → 1 are not.

Two cycles are considered to be different if one or more of the rooms visited in the first cycle is not in the second cycle.

Return the confusion score of the maze.

Constraints:

  • 2≤2 \leq n ≤100\leq 100
  • 1≤1 \leq corridors.length ≤5×102\leq 5 \times 10^2
  • corridors[i].length =2= 2
  • 1≤room1i,room2i≤n1 \leq room1_i, room2_i \leq n
  • room1i≠room2iroom1_i \neq room2_i
  • There are no duplicate corridors.
⋮
Tap here to switch tabs
Problem
Submissions

Problem: Paths in Maze That Lead to Same Room

Paths in Maze That Lead to Same Room counts the maze's confusion score: the number of distinct cycles using exactly three rooms, given an undirected corridor list.

Statement

A maze consists of nn rooms numbered from 1−n1 - n, and some rooms are connected by corridors. You are given a 2D integer array, corridors, where corridors[i]=[room1,room2]corridors[i] = [room1, room2] indicates that there is a corridor connecting room1room1 and room2room2, allowing a person in the maze to go from room1room1 to room2room2 and vice versa.

The designer of the maze wants to know how confusing the maze is. The confusion score of the maze is the number of different cycles of length 3.

For example, 1→2→3→11 → 2 → 3 → 1 is a cycle of length 33, but 1→2→3→41 → 2 → 3 → 4 and 1→2→3→2→11 → 2 → 3 → 2 → 1 are not.

Two cycles are considered to be different if one or more of the rooms visited in the first cycle is not in the second cycle.

Return the confusion score of the maze.

Constraints:

  • 2≤2 \leq n ≤100\leq 100
  • 1≤1 \leq corridors.length ≤5×102\leq 5 \times 10^2
  • corridors[i].length =2= 2
  • 1≤room1i,room2i≤n1 \leq room1_i, room2_i \leq n
  • room1i≠room2iroom1_i \neq room2_i
  • There are no duplicate corridors.