-
Notifications
You must be signed in to change notification settings - Fork 0
/
endpscopy_hardBFS.cpp
125 lines (123 loc) · 2.89 KB
/
endpscopy_hardBFS.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <bits/stdc++.h>
using namespace std;
class node{
public:
int left;
int right;
int up;
int down;
};
void allot(int n,int i, int j, vector<vector<node>> &move){
node cell;
if(n==1){
cell.left=1;
cell.right=1;
cell.up=1;
cell.down=1;
}
else if(n==2){
cell.left=0;
cell.right=0;
cell.up=1;
cell.down=1;
}
else if(n==3){
cell.left=1;
cell.right=1;
cell.up=0;
cell.down=0;
}
else if(n==4){
cell.left=0;
cell.right=1;
cell.up=1;
cell.down=0;
}
else if(n==5){
cell.left=0;
cell.right=1;
cell.up=0;
cell.down=1;
}
else if(n==6){
cell.left=1;
cell.right=0;
cell.up=0;
cell.down=1;
}
else if(n==7){
cell.left=1;
cell.right=0;
cell.up=1;
cell.down=0;
}
else{
cell.left=0;
cell.right=0;
cell.up=0;
cell.down=0;
}
move[i][j]=cell;
}
bool isValid(int n,int m,int r,int c){
return r>=0 && r<n && c>=0 && c<m;
}
int endoscope(){
int n,m,r,c,len;
cin>>n>>m>>r>>c>>len;
vector<vector<int>> vis(n,vector<int>(m,0));
vector<vector<int>> grid(n,vector<int>(m));
vector<vector<node>> move(n,vector<node>(m));
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
cin>>grid[i][j];
allot(grid[i][j],i,j,move);
}
}
if(grid[r][c]==0) return 0;
queue<vector<int>> q;
vis[r][c]=1;
int cnt=1;
q.push({r,c,1});
while(!q.empty()){
int row=q.front()[0];
int col=q.front()[1];
int steps=q.front()[2];
// cout<<"run"<<endl;
q.pop();
if(1+steps<=len){
if(isValid(n,m,row-1,col) && !vis[row-1][col] && move[row][col].up && move[row-1][col].down){
q.push({row-1,col,steps+1});
vis[row-1][col]=1;
cnt++;
}
if(isValid(n,m,row+1,col) && !vis[row+1][col] && move[row+1][col].up && move[row][col].down){
q.push({row+1,col,steps+1});
vis[row+1][col]=1;
cnt++;
}
if(isValid(n,m,row,col-1) && !vis[row][col-1] && move[row][col].left && move[row][col-1].right){
q.push({row,col-1,steps+1});
vis[row][col-1]=1;
cnt++;
}
if(isValid(n,m,row,col+1) && !vis[row][col+1] && move[row][col+1].left && move[row][col].right){
q.push({row,col+1,steps+1});
vis[row][col+1]=1;
cnt++;
}
// else{
// cout<<"NO RUN"<<endl;
// }
}
}
return cnt;
}
int main(){
int t; cin>>t;
while(t--){
// cout<<"Case#"<<t<<endl;
cout<<endoscope()<<endl;
}
return 0;
}