Untitled
plain_text
2 months ago
2.7 kB
1
Indexable
Never
#include <iostream> using namespace std; int head = -1; int tail = -1; int queue[40009]; int queue1[40009]; void Enqueue(int queue[], int queue1[], int element,int element1, int& tail) { queue[tail] = element; queue1[tail] = element1; tail++; } void Dequeue(int queue[], int queue1[], int& head) { queue[head] = 0; queue1[head] = 0; head++; } int Front(int queue[], int head) { return queue[head]; } int main(){ //freopen("input.txt","r",stdin); int T; cin >> T; for(int TestCase = 0;TestCase < T;TestCase++){ int size; cin >> size; head = -1; tail = -1; int arr[201][201]; int array[201][201]; int x,y; int check = -1; for (int i = 0;i<size;i++){ for(int j = 0;j<size;j++){ cin >> arr[i][j]; array[i][j] = arr[i][j]; if(arr[i][j] == 2){ arr[i][j] = 1; x = j; y = i; } } } Enqueue(queue,queue1,0,0,tail); arr[0][0] = 2; while(tail-head > 0){ int cow = Front(queue, head); int row = Front(queue1, head); Dequeue(queue,queue1,head); if(row > 0){ if(arr[row-1][cow] == 1) { Enqueue(queue,queue1,cow,row-1,tail); arr[row-1][cow] = arr[row][cow]+1; } } if(row < size-1){ if(arr[row+1][cow] == 1) { Enqueue(queue,queue1,cow,row+1,tail); arr[row+1][cow] = arr[row][cow]+1; } } if(cow > 0){ if(arr[row][cow-1] == 1) { Enqueue(queue,queue1,cow-1,row,tail); arr[row][cow-1] = arr[row][cow]+1; } } if(cow < size-1){ if(arr[row][cow+1] == 1) { Enqueue(queue,queue1,cow+1,row,tail); arr[row][cow+1] = arr[row][cow]+1; } } } int count = arr[y][x]; if(count != 1){ head = -1; tail = -1; Enqueue(queue,queue1,x,y,tail); array[y][x] = 2; while(tail-head > 0){ int cow = Front(queue, head); int row = Front(queue1, head); Dequeue(queue,queue1,head); if(row > 0){ if(array[row-1][cow] == 1) { Enqueue(queue,queue1,cow,row-1,tail); array[row-1][cow] = array[row][cow]+1; } } if(row < size-1){ if(array[row+1][cow] == 1) { Enqueue(queue,queue1,cow,row+1,tail); array[row+1][cow] = array[row][cow]+1; } } if(cow > 0){ if(array[row][cow-1] == 1) { Enqueue(queue,queue1,cow-1,row,tail); array[row][cow-1] = array[row][cow]+1; } } if(cow < size-1){ if(array[row][cow+1] == 1) { Enqueue(queue,queue1,cow+1,row,tail); array[row][cow+1] = array[row][cow]+1; } } } if(array[size-1][size-1] > 1){ check = count + array[size-1][size-1]-4; } } cout << check << endl; } return 0; }