//hugo_bandau_duong_ong
duyvan
plain_text
2 years ago
1.9 kB
11
Indexable
#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;
}Editor is loading...
Leave a Comment