DATA

STRUCUTURES
AND ALGORITHMS

CONTENT

• Stack

• Exercise: Check the symmetry of the parentheses

DATA STRUCTURES AND • Queue
ALGORITHMS • Exercise: Find the fastest way out of the maze
Week 8: Stack and Queue

3 4
STACK STACK

 A stack is a Linear Data Structure

 The operation of adding and removing elements on the list is

performed at one end (top) of the list according to the Last In
First Out principle (the last element added to the stack is the first
element to be removed)).

 Basic operations with stack S:

• Push(x, S): insert element x into the stack
• Pop(S): remove the first element from the stack
• Top(S): Access the element at the top of the stack
• isEmpty(S): Returns true if the stack is empty

Nguồn: https://en.wikipedia.org/wiki/Stack_%28abstract_data_type%29

5 6

IMPLEMENT STACKS WITH SINGLY LINKED LIST IMPLEMENT STACKS WITH SINGLY LINKED LIST

• Data structures and Initialization • Push

Create a new node

Declare a struct for each
element of a stack If the stack is empty, return the
created node

If the stack is not empty, the

Create a node of the stack newly created node becomes
the head of the list

7 8
IMPLEMENT STACKS WITH SINGLY LINKED LIST IMPLEMENT STACKS WITH SINGLY LINKED LIST

• Pop • Top and IsEmpty

If the stack is empty, return null

If the stack is not empty, delete the

top element of the stack and return
the top element of the stack

9 10

SOME APPLICATIONS OF STACKS SOME APPLICATIONS OF STACKS

 Function call stack: Stack is widely used to manage function calls and local  Backtracking Algorithms: In algorithms like depth-first search (DFS) and
variables in programming languages. When a function is called, its context backtracking algorithms (For example, solving puzzles like the N-Queens problem
(including arguments and local variables) is pushed onto the stack. When the or Sudoku), a stack can be used to keeps track of which nodes or states have been
function returns, its context is pushed off the stack, allowing correct nesting of visited. This allows for easy backtracking to explore alternatives when needed.
the function.
 Expression Analysis: Stack is used to analyze and understand expressions in
 Undo mechanism: Stacks are used in applications that require the Undo feature,
compilers and interpreters. They help maintain operator precedence and evaluate
such as text editors, graphics software, or version management systems. Each
expressions correctly.
user action can be pushed onto the stack, and undoing an action involves taking it
off the stack to revert the change.

11 12
SOME APPLICATIONS OF STACKS CONTENT

 Memory Management: Stack plays an important role in memory management in • Stack

computer systems. They are used to manage the function call stack, which stores
• Exercise: Check the symmetry of the parentheses
information about function calls and local variables. The stack helps allocate
memory for function calls and free it when functions return, preventing memory • Queue
leaks.
• Exercise: Find the fastest way out of the maze
 Expression Analysis: Stack is used to analyze and understand expressions in
compilers and interpreters. They help maintain operator precedence and evaluate
expressions correctly.

13 14

EXERCISE: CHECK THE SYMMETRY OF THE PARENTHESES EXERCISE: CHECK THE SYMMETRY OF THE PARENTHESES

 Given a sequence of brackets E where each element is a bracket of one of the

 Data:
following types: (, ), [, ], {, }. Write a program to check whether the parentheses are stdin stdout

symmetric or not? • A single line containing a string of ()[{}([])] 1

characters representing a
 Example:
sequence of parentheses
• ( ) [ { } ( [ ] ) ]: symmetric stdin stdout
• Result: ()[{}([]}] 0
• ( ) [ { } ( [ ] } ]: non-symmetric
• Write 1 if the bracket sequence is
symmetrical and 0 if the bracket
sequence is not symmetrical

15 16
EXERCISE: CHECK THE SYMMETRY OF THE PARENTHESES EXAMPLE

 Algorithm  EXAMPLE 1: Sequence ( ) [ ( { } ) ]

 Initialize an empty stack S • Initialize an empty stack, traverse the parentheses from left to
 Browse the parentheses from left to right right
 If you encounter an opening parenthesis A, put that opening parenthesis in S

 If you encounter a closing parenthesis B

 If S is empty, the conclusion is that the parenthesis sequence E is not symmetrical

 If S is not empty

 Takes an opening parenthesis A from the stack S

 If A and B are not symmetrical (opening and closing brackets are of different types), then the conclusion is that E is
not symmetrical

 At the end of the review, if S is not empty, the conclusion is that E is not symmetric, otherwise E is symmetric

17 18

EXAMPLE EXAMPLE

 Example 1: sequence ( ) [ ( { } ) ]  Example 1: sequence ( ) [ ( { } ) ]

• Step 1: Consider the next parenthesis as the opening parenthesis “(“ -> put
• Step 1: Consider the next parenthesis as the opening the opening parenthesis on the stack
parenthesis “(“ -> put the opening parenthesis on the • Step 2: Consider the next parenthesis as the closing parenthesis “)” -> remove
stack the opening parenthesis from the stack and match “(“ “)” -> the result is correct
so we continue browsing

19 20
EXAMPLE EXAMPLE

 Example 1: sequence ( ) [ ( { } ) ]  Example 1: sequence ( ) [ ( { } ) ]

• Step 1: Consider the next parenthesis as the opening parenthesis “(“ -> put • Step 1: Consider the next parenthesis as the opening parenthesis “(“ -> put
the opening parenthesis on the stack the opening parenthesis on the stack
• Step 2: Consider the next parenthesis as the closing parenthesis “)” -> remove • Step 2: Consider the next parenthesis as the closing parenthesis “)” -> remove
the opening parenthesis from the stack and match “(“ “)” -> the result is correct the opening parenthesis from the stack and match “(“ “)” -> the result is correct
so we continue browsing so we continue browsing
• Step 3: Encounter opening parenthesis “[“ -> put this opening parenthesis on • Step 3: Encounter opening parenthesis “[“ -> put this opening parenthesis on
the stack the stack
• Step 4: Encounter the opening parenthesis “(“  put this opening parenthesis
on the stack

(
[ [

21 22

EXAMPLE EXAMPLE

 Example 1: sequence ( ) [ ( { } ) ]  Example 1: sequence ( ) [ ( { } ) ]

• Step 1: Consider the next parenthesis as the opening parenthesis “(“ -> put • Step 1: Consider the next parenthesis as the opening parenthesis “(“ -> put the opening
the opening parenthesis on the stack parenthesis on the stack
• Step 2: Consider the next parenthesis as the closing parenthesis “)” -> remove the
• Step 2: Consider the next parenthesis as the closing parenthesis “)” -> remove
opening parenthesis from the stack and match “(“ “)” -> the result is correct so we
the opening parenthesis from the stack and match “(“ “)” -> the result is correct
continue browsing
so we continue browsing
• Step 3: Encounter opening parenthesis “[“ -> put this opening parenthesis on the stack
• Step 3: Encounter opening parenthesis “[“ -> put this opening parenthesis on
• Step 4: Encounter the opening parenthesis “(“ -> put this opening parenthesis on the
the stack stack
• Step 4: Encounter the opening parenthesis “(“ -> put this opening parenthesis • Step 5: Encounter opening parenthesis “{“ -> put this opening parenthesis on the stack
on the stack • Step 6: Encounter a closing parenthesis “}” -> take an opening parenthesis “{“ out of the
{
• Step 5: Encounter opening parenthesis “{“ -> put this opening parenthesis on stack
the stack ( • Matches “{“ “}” -> the result is correct -> continue
(
[ [

23 24
EXAMPLE EXAMPLE

 Example 1: sequence ( ) [ ( { } ) ]  Example 1: sequence ( ) [ ( { } ) ]

• Step 6: Encounter a closing parenthesis “}” -> take an opening parenthesis “{“ out of • Step 6: Encounter a closing parenthesis “}” -> take an opening parenthesis “{“ out of
the stack the stack
• Matches “{“ “}” -> the result is correct -> continue • Matches “{“ “}” -> the result is correct -> continue
• Step 7: Encounter a closing parenthesis “)” -> take an opening parenthesis “(“ out of • Step 7: Encounter a closing parenthesis “)” -> take an opening parenthesis “(“ out of
the stack the stack
• Matches “(“ “)” -> the result is correct -> continue • Matches “(“ “)” -> the result is correct -> continue
• Step 8: Encounter a closing parenthesis “]” -> take an opening parenthesis “[“ out of
the stack
• Match “[“ “]” -> now the parenthesis sequence has been reviewed and the stack
is empty, so the result of this parenthesis sequence is symmetrical

25 26

EXAMPLE EXAMPLE

 Example 2: Sequence ( ) [ ( } } ) ]  Example 2: sequence ( ) [ ( } } ) ]

• Step 1: The next parenthesis is the opening parenthesis "(" -> put this
• Initialize an empty stack and traverse the parentheses from
opening parenthesis on the stack
left to right

27 28
EXAMPLE EXAMPLE

 Example 2: sequence ( ) [ ( } } ) ]  Example 2: sequence ( ) [ ( } } ) ]

• Step 1: The next parenthesis is the opening parenthesis "(" -> put this • Step 1: The next parenthesis is the opening parenthesis "(" -> put this
opening parenthesis on the stack opening parenthesis on the stack
• Step 2: Encounter the next closing parenthesis ")" -> take an opening • Step 2: Encounter the next closing parenthesis ")" -> take an opening
parenthesis "(" out of the stack parenthesis "(" out of the stack
• Step 3: Encounter the next parenthesis, the opening parenthesis “[“ -> put
this opening parenthesis on the stack

29 30

EXAMPLE EXAMPLE

 Example 2: sequence ( ) [ ( } } ) ]  Example 2: sequence ( ) [ ( } } ) ]

• Step 1: The next parenthesis is the opening parenthesis "(" -> put this • Step 1: The next parenthesis is the opening parenthesis "(" -> put this
opening parenthesis on the stack opening parenthesis on the stack
• Step 2: Encounter the next closing parenthesis ")" -> take an opening • Step 2: Encounter the next closing parenthesis ")" -> take an opening
parenthesis "(" out of the stack parenthesis "(" out of the stack
• Step 3: Encounter the next parenthesis, the opening parenthesis “[“ -> put • Step 3: Encounter the next parenthesis, the opening parenthesis “[“ -> put
this opening parenthesis on the stack this opening parenthesis on the stack
• Step 4: The next parenthesis is the opening parenthesis "(" -> put this • Step 4: The next parenthesis is the opening parenthesis "(" -> put this
opening parenthesis on the stack opening parenthesis on the stack
• Step 5: Encounter the next parenthesis, the closing parenthesis “}” -> take
out an opening parenthesis, the parenthesis “(“:
(
• Match “(“ “}” -> the matching result is wrong, so we conclude that the
[ given parentheses are not symmetric. [

31 32
IMPLEMENTATION IMPLEMENTATION

#include <stdio.h> #include <stdio.h> void push(char c){

#include <string.h> #include <string.h> Node* p = makeNode(c);
#include <stdlib.h> #include <stdlib.h> p->next = top; top = p;
typedef struct Node{ typedef struct Node{ }
char c; char c; char pop(){
struct Node* next; struct Node* next; if(top == NULL) return ' ';
}Node; }Node; Node* tmp = top; top = top->next;
Node* top; Node* top; char res = tmp->c;
char s[1000001]; char s[1000001]; free(tmp);
Node* makeNode(char c){ Node* makeNode(char c){ return res;
Node* p=(Node*)malloc(sizeof(Node)); Node* p=(Node*)malloc(sizeof(Node)); }
p->c = c; p->next = NULL; return p; p->c = c; p->next = NULL; return p;
} }

33 34

IMPLEMENTATION IMPLEMENTATION

int match(char a, int b){ int match(char a, int b){ int check(char* s){
if(a == '(' && b == ')') return 1; if(a == '(' && b == ')') return 1; for(int i = 0; i < strlen(s); i++){
if(a == '{' && b == '}') return 1; if(a == '{' && b == '}') return 1; if(s[i] == '(' || s[i] == '{' || s[i] == '[')
if(a == '[' && b == ']') return 1; if(a == '[' && b == ']') return 1; push(s[i]);
return 0; return 0; else{
} } if(top==NULL) return 0;
char o = pop();
if(!match(o,s[i])) return 0;
}
}
return top == NULL;
}

35 36
IMPLEMENTATION CONTENT

int match(char a, int b){ int check(char* s){

• Stack
if(a == '(' && b == ')') return 1; for(int i = 0; i < strlen(s); i++){
if(s[i] == '(' || s[i] == '{' || s[i] == '[')
if(a == '{' && b == '}') return 1;
• Exercise: Check the symmetry of the parentheses
if(a == '[' && b == ']') return 1; push(s[i]);
else{
return 0;
if(top==NULL) return 0;
• Queue
}
char o = pop();
int main(){ if(!match(o,s[i])) return 0;
• Exercise: Find the fastest way out of the maze
scanf("%s",s); }
int res = check(s); }
printf("%d",res); return top == NULL;
return 0; }
}

37 38

QUEUE ILLUSTRATION THE OPERATIONS OF A QUEUE

 A queue is a linear data structure with two ends, head Queue Returned
and tail Operation state element
9
 The operation of adding new elements is performed in
Front / Head Back / Tail / Rear

the tail. The operation of removing elements is 3 4 5 6 7 8 Enqueue

Dequeue
performed in the head
 Operating principle: FIFO – First In First Out 2

 Basic operations on Q queue: Idea of a queue

 enqueue(x, Q): insert element x into the queue

 dequeue(Q): remove an element from the queue
 isEmpty(Q): returns true if the queue is empty

Source: https://www.geeksforgeeks.org/queue-data-structure/

39 40
IMPLEMENT A QUEUE WITH A SINGLY LINKED LIST IMPLEMENT A QUEUE WITH A SINGLY LINKED LIST

• Data structure and Initialization • Enqueue

Create a new node

Declare a struct for each element of
a queue
If the queue is empty, return the
newly created element

If the queue is not empty, make

Create a node (element) for the the newly created node the
queue head of the list

41 42

IMPLEMENT A QUEUE WITH A SINGLY LINKED LIST SOME APPLICATIONS OF QUEUES

• Dequeue
 Breadth First Search (BFS): BFS is an algorithm for traversing or searching in tree
If the queue is empty, return NULL
and graph data structures. It uses a queue to discover nodes level by level, making
it an important tool for solving graph-related problems.

 Task scheduling: Queues are used in operating systems to schedule tasks or

If the queue has only one element
processes for execution. Tasks are placed into a queue and the operating system
executes them in the order they are added, ensuring fairness in resource
If the queue has more than one element, get distribution.
the last element of the list

43 44
SOME APPLICATIONS OF QUEUES SOME APPLICATIONS OF QUEUES

 Web server request handling: Web servers use queues to manage incoming HTTP  Task management in multithreading: In multithreaded applications, queues can be
requests. Each incoming request is placed into a queue and processed by threads used to manage tasks that need to be executed concurrently. Execution threads
or workflows, allowing the server to process multiple requests at once. remove tasks from the queue and execute the corresponding work.

 Buffering in I/O operations: Queues are used to buffer data during I/O operations.  Order fulfillment in warehouses: In logistics and storage management, queues can
For example, when data is read from a file or network drive, it is often placed in a be used to manage the order fulfillment process. Orders are placed into a queue
queue before processing to smooth out variations in the rate at which the data is for selection, packing and delivery to ensure efficient processing.
received.

45 46

CONTENT MAZE

 Problem: A rectangular maze is represented by a 0-1 NxM matrix in which A[i,j] = 1

• Stack
represents cell (i,j) as a brick wall and A[i,j] = 0 represents cell ( i,j) are empty cells and
• Exercise: Check the symmetry of the parentheses can be moved into. From an empty cell, we can move to 1 of 4 neighboring cells (up,
down, left, right) if that cell is empty.
• Queue 1 2 3 4 5 6 7 8 9 10 11 12
• Starting from an empty call in the 1
• Exercise: Find the fastest way out of the maze maze, find the shortest way out of
2
3
the maze 4
5 X
6
7
8

47 7 bước 48
MAZE MAZE

 Data:  Data:

• Line 1: write 4 positive integers n, m, r, c in which n and m are respectively the number of rows • Line 1: write 4 positive integers n, m, r, c in which n and m are respectively the number of rows
and columns of matrix A (1 <= n,m <= 999) and r, c are the indexes respectively. Row and and columns of matrix A (1 <= n,m <= 999) and r, c are the indexes respectively. Row and
column numbers of the starting cell. column numbers of the starting cell.

• Line i+1 (i=1,...,n): the ith line of matrix A • Line i+1 (i=1,...,n): the ith line of matrix A

• Result: • Result:

• Write the shortest number of steps needed to exit the maze, or write the value -1 if no path • Write the shortest number of steps needed to exit the maze, or write the value -1 if no path
can be found to exit the maze.. can be found to exit the maze..

49 50

MAZE ALGORITHM

 The breadth-first search algorithm finds the shortest path on the state transition model:
Example:
stdin stdout  Initial state
8 12 5 6 7
110000100001
 Target state
Initial state
100011010011
001000000000  Each state s will have a set of N(s) of
100000100101
100100000100
101010001010 neighboring states
000010100000
101101110101

Target state

51 52
ALGORITHM ILLUSTRATION

 The breadth-first search algorithm finds the shortest path on the state transition model: 1 2 3 4 5 6 7 8 9 10 11 12
1
2
findPath(s0, N){
3
Init Queue
Queue.PUSH(s0); Initial state 4
visited[s0] = true; 5
while Queue not empty do{ X
s = Queue.POP(); 6
for x  N(s) do{
7
if not visited[x] and check(x) then{
if target(x) then Initialize an empty Q queue 8
return x;
else{ Insert state (5,6) into Q
Queue.PUSH(x);
visited[x] = true;
} Target state (5,6)
}
}
}
}
53 54

ILLUSTRATION ILLUSTRATION

1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12
1 1
2 2
3 3
4 4
5 X 5 X
6 6
7 7
Take (5,6) out of Q 8 Take (5,7) out of Q 8

Put the state (5,7), (5, 5), (4, 6), (6,6) into Q Put states (6,7), (5, 8) into Q
(5,6) (5,7) (5,5) (4,6) (6,6) (5,7) (5,5) (4,6) (6,6) (6,7) (5,8)

55 56
ILLUSTRATION ILLUSTRATION

1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12
1 1
2 2
3 3
4 4
5 X 5 X
6 6
7 7
Take (5,5) out of Q 8 Take (4,6) out of Q 8

Insert state (4,5) into Q Insert state (3,6) into Q

(5,5) (4,6) (6,6) (6,7) (5,8) (4,5) (4,6) (6,6) (6,7) (5,8) (4,5) (3,6)

57 58

ILLUSTRATION ILLUSTRATION

1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12
1 1
2 2
3 3
4 4
5 X 5 X
6 6
7 7
Take (6,6) out of Q 8 Take (6,7) out of Q 8

Insert state (7,6) into Q Insert state (6,8) into Q

(6,6) (6,7) (5,8) (4,5) (3,6) (7,6) (6,7) (5,8) (4,5) (3,6) (7,6) (6,8)

59 60
ILLUSTRATION ILLUSTRATION

1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12
1 1
2 2
3 3
4 4
5 X 5 X
6 6
7 7
Take (5,8) out of Q 8 Take (4,5) out of Q 8

Insert states (5,9) and (4,8) into Q Insert states (4,4) and (3,5) into Q
(5,8) (4,5) (3,6) (7,6) (6,8) (5,9) (4,8) (4,5) (3,6) (7,6) (6,8) (5,9) (4,8) (4,4) (3,5)

61 62

ILLUSTRATION ILLUSTRATION

1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12
1 1
2 2
3 3
4 4
5 X 5 X
6 6
7 7
Take (3,6) out of Q 8 Take (7,6) out of Q 8

Insert state (3,7) into Q No new states can be added to Q

(3,6) (7,6) (6,8) (5,9) (4,8) (4,4) (3,5) (3,7) (7,6) (6,8) (5,9) (4,8) (4,4) (3,5) (3,7)

63 64
ILLUSTRATION ILLUSTRATION

1 2 3 4 5 6 7 8 9 10 11 12
1 1
2 2
3 3
4 4
5 X 5 X
6 6
7 7

Take (6,8) out of Q 8 Take (5,9) out of Q 8

Bring the state (7,8) into Q Bring the state (4,9) into Q
(6,8) (5,9) (4,8) (4,4) (3,5) (3,7) (7,8) (5,9) (4,8) (4,4) (3,5) (3,7) (7,8) (4,9)

65 66

ILLUSTRATION ILLUSTRATION

1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12
1 1
2 2
3 3
4 4
5 X 5 X
6 6
7 7
Take (4,8) out of Q 8 Take (4,4) out of Q 8

Bring the state (3,8) into Q Put the state (4,3), (3,4) into Q
(4,8) (4,4) (3,5) (3,7) (7,8) (4,9) (3,8) (4,4) (3,5) (3,7) (7,8) (4,9) (3,8) (4,3) (3,4)

67 68
ILLUSTRATION ILLUSTRATION

1 2 3 4 5 6 7 8 9 10 11 12
1 1
2 2
3 3
4 4
5 X 5 X
6 6
7 7
Take (3,5) out of Q 8 Take (3,7) out of Q 8
No new states can be added to Q Bring the new state (2,7) into Q

(3,5) (3,7) (7,8) (4,9) (3,8) (4,3) (3,4) (3,7) (7,8) (4,9) (3,8) (4,3) (3,4) (2,7)

69 70

ILLUSTRATION ILLUSTRATION

1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12
1 1
2 2
3 3
4 4
5 X 5 X
6 6
7 7
Take (7,8) out of Q 8 Take (4,9) out of Q 8

Bring new status (7,9) into Q Bring the new state (3,9) into Q
(7,8) (4,9) (3,8) (4,3) (3,4) (2,7) (7,9) (4,9) (3,8) (4,3) (3,4) (2,7) (7,9) (3,9)

71 72
ILLUSTRATION ILLUSTRATION

1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12
1 1
2 2
3 3
4 4
5 X 5 X
6 6
7 7
Take (3,8) out of Q 8 Take (4,3) out of Q 8

No new states can be added to Q Bringing new states (4,2), (5,3) into Q
(3,8) (4,3) (3,4) (2,7) (7,9) (3,9) (4,3) (3,4) (2,7) (7,9) (3,9) (4,2) (5,3)

73 74

ILLUSTRATION ILLUSTRATION

1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12
1 1
2 2
3 3
4 4
5 X 5 X
6 6
7 7

Take (3,4) out of Q 8 Take (2,7) out of Q 8

Bring the new state (2,4) into Q No new states can be added to Q
(3,4) (2,7) (7,9) (3,9) (4,2) (5,3) (2,4) (2,7) (7,9) (3,9) (4,2) (5,3) (2,4)

75 76
ILLUSTRATION ILLUSTRATION

1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12
1 1
2 2
3 3
4 4
5 X 5 X
6 6
7 7
8 Take (3,9) out of Q 8
Take (7,9) out of Q
Bring new states (8,9), (7,10) into Q Bring new states (2,9), (3,10) into Q
(7,9) (3,9) (4,2) (5,3) (2,4) (8,9) (7,10) (3,9) (4,2) (5,3) (2,4) (8,9) (7,10) (2,9) (3,10)

77 78

ILLUSTRATION ILLUSTRATION

1 2 3 4 5 6 7 8 9 10 11 12
1 1
2 2
3 3
4 4
5 X 5 X
6 6
7 7

Take (4,2) out of Q 8 Take (5,3) out of Q 8

Bring new states (3,2), (5,2) into Q No new states can be added to Q
(4,2) (5,3) (2,4) (8,9) (7,10) (2,9) (3,10) (3,2) (5,2) (5,3) (2,4) (8,9) (7,10) (2,9) (3,10) (3,2) (5,2)

79 80
ILLUSTRATION ILLUSTRATION

1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12
1 1
2 2
3 3
4 4
5 X 5 X
6 6
7 7

Take (2,4) out of Q 8 8

Take (8,9) out of Q
Bring the new state (1,4) into Q The target state (9,9) is generated corresponding to the position outside the maze

(2,4) (8,9) (7,10) (2,9) (3,10) (3,2) (5,2) (1,4) (8,9) (7,10) (2,9) (3,10) (3,2) (5,2) (1,4)

81 82

IMPLEMENTATION IMPLEMENTATION

#include <stdio.h> #include <stdio.h> int n,m;

#include <stdlib.h> int A[1000][1000];
#include <stdlib.h>
#include <string.h> int startRow, startCol;
#include <string.h>
typedef struct Node{ int visited[1000][1000];
typedef struct Node{ int row; Node* first;
int row; int col; Node* last;

int col; int step; int dr[4] = {0,0,1,-1};

struct Node* next; int dc[4] = {1,-1,0,0};
int step;
}Node;
struct Node* next;
}Node;

83 84
IMPLEMENTATION IMPLEMENTATION

#include <stdio.h> int n,m; int isEmpty(){

#include <stdlib.h> int A[1000][1000]; return first == NULL && last == NULL;
#include <string.h> int startRow, startCol; }
typedef struct Node{ int visited[1000][1000]; void push(Node* p){
int row; Node* first; if(isEmpty(){
int col; Node* last; first = p; last = p; return;}
int step; int dr[4] = {0,0,1,-1}; last->next = p; last = p;
struct Node* next; int dc[4] = {1,-1,0,0}; }
}Node; Node* makeNode(int r,int c, int step){ Node* pop(){

Node* p = (Node*)malloc(sizeof(Node)); if(isEmpty()) return NULL;

p->row = r; p->col = c; Node* tmp = first; first = first->next;

p->step = step; p->next = NULL; if(first == NULL) last = NULL;

return p; return tmp;

} }
85 86

IMPLEMENTATION IMPLEMENTATION

int isEmpty(){ void input(){ int isEmpty(){ void input(){

return first == NULL && last == NULL; scanf("%d %d %d %d",&n,&m,&sr,&sc); return first == NULL && last == NULL; scanf("%d %d %d %d",&n,&m,&sr,&sc);
} for(int i = 1; i <= n; i++) } for(int i = 1; i <= n; i++)
void push(Node* p){ for(int j = 1; j <= m; j++) void push(Node* p){ for(int j = 1; j <= m; j++)
if(isEmpty(){ scanf("%d",&A[i][j]); if(isEmpty(){ scanf("%d",&A[i][j]);
first = p; last = p; return;} } first = p; last = p; return;} }
last->next = p; last = p; last->next = p; last = p;
} }
Node* pop(){ Node* pop(){
if(isEmpty()) return NULL; if(isEmpty()) return NULL; int targetState(Node* s){
Node* tmp = first; first = first->next; Node* tmp = first; first = first->next; return (s->row < 1 ||
if(first == NULL) last = NULL; if(first == NULL) last = NULL; s->row > n || s->col < 1
return tmp; return tmp; || s->col > m);
} } }
87 88
IMPLEMENTATION IMPLEMENTATION

void init(){ void init(){ int solve(){

first = NULL; last = NULL; first = NULL; last = NULL; init();
for(int i = 0; i <= 1000; i++) for(int i = 0; i <= 1000; i++) while(!isEmpty()){
for(int j = 0; j <= 1000; j++) for(int j = 0; j <= 1000; j++) Node* s = pop();
visited[i][j] = 0; visited[i][j] = 0; for(int k = 0; k < 4; k++){
Node* startState = makeNode(sr,sc,0); Node* startState = makeNode(sr,sc,0); int nr = s->row + dr[k];int nc= s->col + dc[k];
push(startState); visited[sr][sc] = 1; push(startState); visited[sr][sc] = 1; if(visited[nr][nc]==0&& A[nr][nc]==0){
} } Node* ns = makeNode(nr, nc, s->step + 1);
push(ns);visited[nr][nc] = 1;
if(targetState(ns)) return ns->step;
}
}
}
return -1;
}
89 90

IMPLEMENTATION

void init(){ int solve(){

first = NULL; last = NULL; init();
for(int i = 0; i <= 1000; i++) while(!isEmpty()){
for(int j = 0; j <= 1000; j++) Node* s = pop();
visited[i][j] = 0; for(int k = 0; k < 4; k++){

THANK YOU !
Node* startState = makeNode(sr,sc,0); int nr = s->row + dr[k];int nc= s->col + dc[k];
push(startState); visited[sr][sc] = 1; if(visited[nr][nc]==0&& A[nr][nc]==0){
} Node* ns = makeNode(nr, nc, s->step + 1);
push(ns);visited[nr][nc] = 1;
int main(){ if(targetState(ns)) return ns->step;
input(); }
int res = solve(); }
printf("%d",res); }
return 0; return -1;
} }
91 92