Untitled
unknown
plain_text
a year ago
6.4 kB
6
Indexable
#include<iostream> using namespace std; int t, m, n, a[51][51], p, r, c, cnt, ploang; int front , rear,q1[51 * 51] , q2[51 * 51], visited[51][51]; int dx[] = {-1,0,1,0}; int dy[] = {0, 1,0,-1}; //struct Queue //{ // void initQueue() // { // front = rear = -1; // } // // int isEmpty() // { // if(front == rear) // return 1; // // return 0; // } // // void enQueue(int x) // { // rear++; // q[rear] = x; // } // // int deQueue() // { // if(!isEmpty()) // { // front++; // return q[front]; // } // return -1; // } // // // //}; //int noi_ong(int x, int y , int r, int c) //{ // if(a[x][y] == 1) // { // if(a[r][c] == 1) // { // if(r == x -1 && c == y || r == x && c == y + 1 || r == x + 1 && c == y || r == x && c == y -1) // return 1; // } // else if(a[r][c] == 2) // { // if(r == x + 1 && c == y || r == x - 1 && c == y) // return 1; // } // else if(a[r][c] == 3) // { // if(r == x && c == y + 1 || r == x && c == y - 1) // return 1; // } // else if(a[r][c] == 4) // { // if(r == x && c == y - 1 || r == x + 1 && c == y) // return 1; // } // else if(a[r][c] == 5) // { // if(r == x -1 && c == y || r == x && c == y - 1) // return 1; // } // else if(a[r][c] == 6) // { // if(r == x - 1 && c == y || r == x && c == y + 1) // return 1; // } // else if(a[r][c] == 7) // { // if(r == x + 1 && c == y || r == x && c == y + 1) // return 1; // } // } // else if(a[x][y] == 2) // { // if(a[r][c] == 1) // { // if(r == x - 1 && c == y || r == x + 1 && c == y) // return 1; // } // else if(a[r][c] == 2) // { // if(r == x - 1 && c == y || r == x + 1 && c == y) // return 1; // } // else if(a[r][c] == 4) // { // if(r == x + 1 && c == y) // return 1; // } // else if(a[r][c] == 5) // { // if(r == x - 1 && c == y) // return 1; // } // else if(a[r][c] == 6) // { // if(r == x - 1 && c == y) // return 1; // } // else if(a[r][c] == 7) // { // if(r == x + 1 && c == y) // return 1; // } // } // else if(a[x][y] == 3) // { // if(a[r][c] == 1) // { // if(r == x && c == y + 1 || r == x && c == y - 1) // return 1; // } // else if(a[r][c] == 3) // { // if(r == x && c == y + 1 || r == x && c == y - 1) // return 1; // } // else if(a[r][c] == 4) // { // if(r == x && c == y - 1) // return 1; // } // else if(a[r][c] == 5) // { // if(r == x && c == y - 1) // return 1; // } // else if(a[r][c] == 6) // { // if(r == x && c == y + 1) // return 1; // } // else if(a[r][c] == 7) // { // if(r == x && c == y + 1) // return 1; // } // } // else if(a[x][y] == 4) // { // if(a[r][c] == 1) // { // if(r == x -1 && c == y || r == x && c == y + 1) // return 1; // } // else if(a[r][c] == 2) // { // if(r == x -1 && c == y) // return 1; // } // else if(a[r][c] == 3) // { // if(r == x && c == y + 1) // return 1; // } // else if(a[r][c] == 5) // { // if(r == x -1 && c == y) // return 1; // } // else if(a[r][c] == 6) // { // if(r == x -1 && c == y || r == x && c == y + 1) // return 1; // } // else if(a[r][c] == 7) // { // if(r == x && c == y + 1) // return 1; // } // } // else if(a[x][y] == 5) // { // if(a[r][c] == 1) // { // if(r == x + 1 && c == y || r == x && c == y + 1) // return 1; // } // else if(a[r][c] == 2) // { // if(r == x + 1 && c == y) // return 1; // } // else if(a[r][c] == 3) // { // if(r == x && c == y + 1) // return 1; // } // else if(a[r][c] == 4) // { // if(r == x + 1 && c == y) // return 1; // } // else if(a[r][c] == 7) // { // if(r == x + 1 && c == y || r == x && c == y + 1) // return 1; // } // else if(a[r][c] == 6) // { // if(r == x && c == y + 1) // return 1; // } // } // else if(a[x][y] == 6) // { // if(a[r][c] == 1) // { // if(r == x + 1 && c == y || r == x && c == y - 1) // return 1; // } // else if(a[r][c] == 2) // { // if(r == x + 1 && c == y) // return 1; // } // else if(a[r][c] == 3) // { // if(r == x && c == y - 1) // return 1; // } // else if(a[r][c] == 4) // { // if(r == x && c == y - 1 || r == x + 1 && c == y ) // return 1; // } // else if(a[r][c] == 5) // { // if(r == x && c == y -1) // return 1; // } // else if(a[r][c] == 7) // { // if(r == x + 1 && c == y) // return 1; // } // } // else if(a[x][y] == 7) // { // if(a[r][c] == 1) // { // if(r == x - 1 && c == y || r == x && c == y - 1) // return 1; // } // else if(a[r][c] == 2) // { // if(r == x - 1 && c == y) // return 1; // } // else if(a[r][c] == 3) // { // if(r == x && c == y - 1) // return 1; // } // else if(a[r][c] == 4) // { // if(r == x && c == y - 1) // return 1; // } // else if(a[r][c] == 5) // { // if(r == x && c == y -1 || r == x - 1 && c == y) // return 1; // } // else if(a[r][c] == 6) // { // if(r == x - 1 && c == y) // return 1; // } // } // return 0; //} bool ket_noi[8][4] = { {0, 0, 0, 0}, {1, 1, 1, 1}, {1, 0, 1, 0}, {0, 1, 0, 1}, {1, 1, 0, 0}, {0, 1, 1, 0}, {0, 0, 1, 1}, {1, 0, 0, 1} }; void BFS(int x, int y) { q1[++rear] = x; q2[rear] = y; while (front != rear) { int u = q1[++front]; int v = q2[front]; if(visited[u][v] == p) break; for (int k = 0; k < 4; k++) { if(!ket_noi[a[u][v]][k]) continue; int tx = u + dx[k]; int ty = v + dy[k]; if( tx < 0 || tx == n || ty < 0 || ty == m || !a[tx][ty]) continue; // int check = noi_ong(u, v, tx , ty); if(!visited[tx][ty] && ket_noi[a[tx][ty]][(k + 2) % 4] ) { visited[tx][ty] = visited[u][v] + 1; q1[++rear] = tx; q2[rear] = ty; cnt++; } } } } int main() { //freopen("t.txt", "r", stdin); cin >> t; for (int tc = 1; tc <= t; tc++) { cin >> m >> n >> r >> c >> p; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { cin >> a[i][j]; visited[i][j] = 0; } } cnt = 1; visited[r][c] = 1; front = -1; rear = -1 ; BFS(r, c); cout <<"Case #" << tc << endl<< cnt << endl; } return 0; }
Editor is loading...
Leave a Comment