Untitled
unknown
plain_text
2 years ago
2.8 kB
3
Indexable
#include <iostream> using namespace std; #define MAX_SIZE 10000000 int Arx[MAX_SIZE]; int Ary[MAX_SIZE]; int Cnt[MAX_SIZE]; int Trangthai[MAX_SIZE]; int front = -1, rear = -1; int N, M; int xbgin, ybgin, xend, yend; class queue { public: bool isEmpty(); void enqueue(int arx, int ary, int cnt, int trangthai); void dequeue(); void peek(int& arx, int& ary, int& cnt, int &trangthai); }; bool queue::isEmpty() { if (front == rear) { return true; } return false; } void queue::enqueue(int arx, int ary, int cnt, int trangthai) { front++; Arx[front] = arx; Ary[front] = ary; Cnt[front] = cnt; Trangthai[front] = trangthai; } void queue::dequeue() { rear++; } void queue::peek(int& arx, int& ary, int& cnt, int &trangthai) { arx = Arx[rear + 1]; ary = Ary[rear + 1]; cnt = Cnt[rear + 1]; trangthai = Trangthai[rear + 1]; } char arr[201][201]; int ard[201][201]; void reset(char ar[201][201]) { for (int i = 0; i < 201; i++) { for (int j = 0; j < 201; j++) { ar[i][j] = 0; ard[i][j] = 0; } } } int dx[] = { -1, 0, 0, 1 }; int dy[] = { 0, 1, -1, 0 }; void BFS(int x1, int y1, int x2,int y2) { int th; int cnt = 1; // dung de dem so lan quay dau if (x1 == x2) { th = 1; } else { th = 0; } queue qe; qe.enqueue(x1, y1, cnt, th); ard[x2][y2] = cnt; ard[x1][y1] = cnt; while (!qe.isEmpty()) { int x, y; qe.peek(x, y, cnt , th); qe.dequeue(); for (int i = 0; i < 4; i++) { int t = x + dx[i]; int k = y + dy[i]; if (t >= 0 && t < N && k >= 0 && k < M) { // trang thai tai phan tu t , k int th1; if (t == x) { th1 = 1; } else { th1 = 0; } int cnt2; // neu trang thai khac nhau cnt++ if (th != th1) { cnt2 = cnt + 1; } else { cnt2 = cnt; } if (ard[t][k] == 0 && arr[t][k] == '0') { qe.enqueue(t, k, cnt2, th1); ard[t][k] = cnt2; } else if(arr[t][k] == '0') { if (cnt < ard[t][k]) { qe.enqueue(t, k, cnt2, th1); ard[t][k] = cnt2; } } } } } } int main() { int testcase; cin >> testcase; for (int tc = 1; tc <= testcase; tc++) { cin >> M >> N; reset(arr); cin >> ybgin >> xbgin >> yend >> xend; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { cin >> arr[i][j]; } } for (int i1 = 0; i1 < 4; i1++) { int x = xbgin - 1 + dx[i1]; int y = ybgin - 1 + dy[i1]; if (arr[x][y] == '0') { BFS(x, y, xbgin - 1, ybgin - 1); } } cout << "#" << tc << " " << ard[xend -1][yend -1] - 1 << endl; } }
Editor is loading...