//hugo_bandau_duong_ong
duyvan
plain_text
21 days ago
1.9 kB
3
Indexable
Never
#include <iostream> using namespace std; int dx[] = {0,0,-1,1};//trai phai tren duoi int dy[] = {-1,1,0,0}; int T, N, M, hx, hy, P; int a[55][55]; int visit[55][55]; int ans; //trai-phai-tren-duoi int vec0[8] = {0,1,0,1,0,0,1,1}; //trai int vec1[8] = {0,1,0,1,1,1,0,0}; int vec2[8] = {0,1,1,0,1,0,0,1}; int vec3[8] = {0,1,1,0,0,1,1,0}; struct Node{ int r,c; }; Node queue[1000001]; int front, rear; void en(int x, int y){ Node node; node.r = x; node.c = y; rear++; queue[rear] = node; } Node de(){ front++; return queue[front]; } void nhap(){ cin >> N >> M >> hx >> hy >> P; for(int i=0; i<N; i++){ for(int j=0; j<M; j++){ cin >> a[i][j]; visit[i][j] = -1; } } } int check(int x, int y, int nx, int ny, int vec){ if(vec == 0){ if(vec0[a[x][y]] == vec1[a[nx][ny]] && vec0[a[x][y]] == 1)return 1; } if(vec == 1){ if(vec1[a[x][y]] == vec0[a[nx][ny]] && vec1[a[x][y]] == 1)return 1; } if(vec == 2){ if(vec2[a[x][y]] == vec3[a[nx][ny]] && vec2[a[x][y]] == 1)return 1; } if(vec == 3){ if(vec3[a[x][y]] == vec2[a[nx][ny]] && vec3[a[x][y]] == 1)return 1; } return 0; } void solve(){ front = rear = -1; en(hx, hy); visit[hx][hy] = 0; while(front != rear){ Node node = de(); for(int k=0; k<4; k++){ int nx = node.r + dx[k]; int ny = node.c + dy[k]; if(nx>=0 && nx<N && ny>=0 && ny<M && visit[nx][ny] == -1 && a[nx][ny] != 0 && visit[node.r][node.c]+1<P){ if(check(node.r,node.c,nx,ny,k) == 1){ en(nx,ny); visit[nx][ny] = visit[node.r][node.c] + 1; ans++; } } } } } int main(){ // freopen("INP.txt","r",stdin); cin >> T; for(int tc=1; tc<=T; tc++){ nhap(); ans = 0; if(a[hx][hy] == 0){ ans = -1; } else solve(); cout << "Case #" << tc << endl; cout << ans+1 << endl; } return 0; }
Leave a Comment