Untitled
unknown
plain_text
a year ago
2.5 kB
7
Indexable
#include<iostream> using namespace std; char mang[100][100]; bool vt[100][100]; int dis[100][100]; const int maxn = 10000; int dx[] = {0, 1, 1, 2, 2, -1, -1, -2, -2}; int dy[] = {0, 2, -2, 1, -1, 2, -2, 1, -1}; int cx[] = {0,0,1,-1,-1,-1,1,1}; int cy[] = {1,-1,0,0,-1,1,-1,1}; int t, n, m; struct point { int x, y; }; class Queue{ private: point arr[maxn]; int front, rear; public: Queue() { front = rear = -1; } bool isFull() { if (rear == maxn - 1) return true; return false; } bool isEmpty() { if (rear == front) return true; return false; } void enQueue(point val) { if (!isFull()) { rear++; arr[rear].x = val.x; arr[rear].y = val.y; } } point deQueue() { point s; if (!isEmpty()) { front++; s.x=arr[front].x; s.y=arr[front].y; } return s; } void reset() { front = rear = -1; } }; Queue myQueue; point p,st,en; void bfs(point start, point end) { myQueue.reset(); myQueue.enQueue(start); while (!myQueue.isEmpty()) { p = myQueue.deQueue(); for (int i = 0; i < 8; i++) { int a = p.x + cx[i]; int b = p.y + cy[i]; if (a >= 0 && b >= 0 && a < n && b < m && vt[a][b] == true) { dis[a][b] = dis[p.x][p.y] + 1; vt[a][b] = false; point poi = {a,b}; myQueue.enQueue(poi); } if (a == end.x && b == end.y) return; } } } void mark() { for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (mang[i][j] == 'Z') { for (int k = 0; k < 9; k++) { int nextMovex = i + dx[k]; int nextMovey = j + dy[k]; if (nextMovex >= 0 && nextMovey >= 0 && nextMovex < n && nextMovey < m ) vt[nextMovex][nextMovey] = false; } } } } vt[en.x][en.y] = true; } void clear() { for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { vt[i][j] = true; dis[i][j] = 0; } } } void nhap() { cin >> n >> m; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> mang[i][j]; if (mang[i][j] == 'A') { st.x = i; st.y = j; } if (mang[i][j] == 'B') { en.x = i; en.y = j; } } } } int main() { cin >> t; for (int tc = 1; tc <= t; tc++) { nhap(); clear(); mark(); bfs(st,en); cout << "Case #" << tc << " "; if (dis[en.x][en.y] == 0) cout << "never" << endl; else cout << dis[en.x][en.y] << endl; } return 0; }
Editor is loading...
Leave a Comment