## Graph - Warm up ``` - - - - - - # - - - - - - - - - - - - - - - - # - ``` 座標? ---- ```c= char maze[n][m]; for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin >> maze[i][j]; ``` 迴圈順序，```i```, ```j``` 位置千萬不能亂動。 ---- P1($x1, y1$), P2($x2, y2$) 1. 曼哈頓距離 :  2. 歐基里德距離 :  3. 柴比雪夫距離 :  ---- ``` # - - - - - - - - - - - - - - - - - - - - - - - - ``` 走到 (3, 2)，怎麼走? ---- ``` - - - - - - - - - - - # - - - - - - - - - - - - - - - - - - - - - # - - - - - - - - - - - - - - ``` 1. manhattan 2. Euclidean 3. chebyshv ---- ```cpp= #include<bits/stdc++.h> using namespace std; int main() { int n, m; cin >> n >> m; char maze[n][m]; int x1 = -1, y1 = -1, x2 = -1, y2 = -1; for(int i=0;i<n;i++) for(int j=0;j<m;j++) { cin >> maze[i][j]; if(maze[i][j] == '#') { if(x1 == -1 && y1 == -1) { x1 = i; y1 = j; } else { x2 = i; y2 = j; } } } //cout << x1 << " " << y1 << " " << x2 << " " << y2; double m_dis, e_dis, c_dis; m_dis = abs(x1 - x2) + abs(y1 -y2); e_dis = sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2)); c_dis = max(abs(x1 - x2), abs(y1 - y2)); cout << m_dis << " " << e_dis << " " << c_dis << "\n"; } ``` ---- Stack ``` # - - @ - - @ - @ - @ - - - - - - @ @ - - - - @ * ``` 記錄點的形式?能到終點? ---- ```c= #include<bits/stdc++.h> using namespace std; struct p{ int x; int y; }; int main() { int n, m; cin >> n >> m; char maze[n][m]; bool judge[n][m]; stack<p> st; for(int i=0;i<n;i++) for(int j=0;j<m;j++) { judge[i][j] = false; cin >> maze[i][j]; if(maze[i][j] == '#') st.push({i, j}); } //int target_x = n - 1, target_y = m - 1; bool flag = false; while(!st.empty()) { p now_p = st.top(); st.pop(); judge[now_p.x][now_p.y] = true; //cout << now_p.x << " " << now_p.y << "\n"; if((now_p.x == n - 1) && (now_p.y == m - 1)) { cout << "YES" << "\n"; flag = true; break; } if((judge[now_p.x][now_p.y - 1] == false) && (now_p.y - 1 >= 0) && (maze[now_p.x][now_p.y - 1] == '-')) st.push({now_p.x, now_p.y - 1}); //up if((judge[now_p.x][now_p.y + 1] == false) && (now_p.y + 1 < m) && (maze[now_p.x][now_p.y + 1] == '-')) st.push({now_p.x, now_p.y + 1}); //dowm if((judge[now_p.x - 1][now_p.y] == false) && (now_p.x - 1 >= 0) && (maze[now_p.x - 1][now_p.y] == '-')) st.push({now_p.x - 1, now_p.y}); //left if((judge[now_p.x + 1][now_p.y] == false) && (now_p.x + 1 < n) && (maze[now_p.x + 1][now_p.y] == '-')) st.push({now_p.x + 1, now_p.y}); //right } if(!flag) cout << "NO" << "\n"; return 0; } ``` ---- 油田 ``` @ @ - - - - - - @ - - - - - - - - - @ @ - - @ @ - - - - - - @ @ - - - @ @ @ - - ``` ---- ```c= #include<bits/stdc++.h> using namespace std; struct p{ int x; int y; }; int main() { int n, m; cin >> n >> m; char oil[n + 5][m + 5]; bool jud[n + 5][m + 5]; stack<p> st; for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { cin >> oil[i][j]; if(oil[i][j] == '#') jud[i][j] = false; else jud[i][j] = true; } } int cnt = 0; for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { if(oil[i][j] == '#' && jud[i][j] == false) { cnt++; st.push({i, j}); //cout << i << " " << j << "\n"; while(!st.empty()) { p now = st.top(); jud[now.x][now.y] = true; st.pop(); if((jud[now.x][now.y - 1] == false) && oil[now.x][now.y - 1] == '#' && (now.y - 1 >= 0)) st.push({now.x, now.y - 1}); if((jud[now.x][now.y + 1] == false) && oil[now.x][now.y + 1] == '#' && (now.y + 1 < n)) st.push({now.x, now.y + 1}); if((jud[now.x - 1][now.y] == false) && oil[now.x + 1][now.y - 1] == '#' && (now.x - 1 >= 0)) st.push({now.x - 1, now.y}); if((jud[now.x + 1][now.y] == false) && oil[now.x + 1][now.y] == '#' && (now.x + 1 < m)) st.push({now.x + 1, now.y}); } } } } cout << cnt << "\n"; } /* ##------ #------- --##--## ------## ---###-- 連通塊(元件) connective unit */ ```