This is the third day of my participation in the August More text Challenge. For details, see: August More Text Challenge

Algorithm design and analysis problem 1: in a bag, when the number of all the balls and > the number product of all the balls, this is a lucky bag

Some of the balls can be removed, but not all, making the removed bag lucky

Input:

(1) N balls

(2) n ball number: A1 a2… an

Output:

The number of lucky bags that can be produced

Core code and comments:

1 1 1 2 2 3 (1) Start from ball 1 (2) Store state: 1 1 1 1 1 2 2 2 1 1 1 1 1 2 2 1 1 1 1 1 1 2 2 1 1 1 1 1 1 2 2 1 1 1 1 2 2 2 2 2 3 3 Void DFS (int step, int local) {if (step > n) return; /* if (step >=2) {int sum = 0; int mul = 0; for (int i = 0; i < step; i++) { sum += store[i]; // sum mul *= store[I]; } if (sum > mul) num++; else return; */ for (int I = local; int I = local; i < N; For (int j = 1; int j = 1; j <= arr[i]; /* for (int k = 0; int k = 0; k < j; k++) { store[step + k] = i; */ DFS (step + j, local + 1); */ DFS (step + j, local + 1); }}}Copy the code

Test results:

Input:

Output:

Algorithm design and Analysis Topic 2: Only adjacent animals can communicate

Input:

N: Number of animals 0… N – 1; M: The number of animals that can communicate with each other

M: Two animals can communicate with each other

K: Query the number of pairs

Each lookup contains 2 numbers (animals)

Output:

What is the minimum number of translations required between 2 animals (shortest path)

-1: The translation does not exist

Core code and comments:

Int BFS(int x, int y) {/* if (G[x][y]! = -1) return G[x][y]; For (int I = 0; i < n; i++) { flag[i] = 0; queue[i][1] = 0x7fffffff; } flag[x] = 1; Int head = 0; int tail = 0; for (int i = 0; i < n; I ++) {/* Find all points adjacent to x and join the queue */ if (I! = x && G[x][i] ! = -1) { queue[tail][0] = i; Queue [tail][1] = 0; // Queue [tail][1] = 0; Flag [I] = 1; tail++; } } while (head ! = tail) { for (int i = 0; i < n; I++) {/* find the unaccessed point and the header element is adjacent to the unaccessed point */ if (! flag[i] && G[queue[head][0]][i] ! = -1) { int temp = queue[head][1] + 1; If (I == y) return temp; if (I == y) return temp; */ queue[tail][0] = I; */ queue[tail][0] = I; queue[tail][1] = temp; flag[i] = 1; tail++; } } head++; } return -1; }Copy the code

Test results:

Input:

3 2

0 1

1 2

2

0 0

0 2

Output: