brave_chiemdat

 avatar
duyvan
plain_text
21 days ago
1.7 kB
1
Indexable
Never
//chiem dat
#include <iostream>
int dx[] = {0,0,-1,1};
int dy[] = {-1,1,0,0};
using namespace std;
int M, N, X, Y, map[10][10], visit[10][10];
int ans;

void nhap(){
    cin >> M >> N >> X >> Y;
    for(int i=1; i<=M; i++){
        for(int j=1; j<=N; j++){
            cin >> map[i][j];
            visit[i][j]=0;
        }
    }
}

void backtrack(int x, int y, int creeps, int cnt){
    if(ans<cnt) ans = cnt;
    for(int k=0; k<4; k++){
        int nx = x+dx[k];
        int ny = y+dy[k];
        if(nx>0 && nx<=M && ny>0 && ny<=N && map[nx][ny]!=0){
            if(2*map[nx][ny]<=creeps && visit[nx][ny]==0){
                visit[nx][ny]=1;
                backtrack(nx,ny,creeps+map[nx][ny],cnt+1);
                visit[nx][ny]=0;
            }
            if(creeps>map[nx][ny] && creeps<2*map[nx][ny] && visit[nx][ny]==0){
                visit[nx][ny]=1;
                backtrack(nx,ny,creeps-map[nx][ny],cnt+1);
                visit[nx][ny]=0;
            }
        }
    }
}

int main(){
    freopen("INP.txt","r",stdin);
//    freopen("OUT.txt","w",stdout);
    int T; cin >> T;
    for(int tc=1; tc<=T; tc++){
        nhap();
        ans = 0;
		visit[X][Y]=1;
        backtrack(X,Y,map[X][Y],1);
		cout <<'#' << tc << " " << ans << endl;
    }

    return 0;
}
/*
#1 12
#2 17
#3 2
#4 1
#5 2
#6 4
#7 2
#8 2
#9 4
#10 8
#11 3
#12 6
#13 2
#14 2
#15 6
#16 32
#17 2
#18 2
#19 29
#20 44
#21 2
#22 22
#23 1
#24 2
#25 1
#26 1
#27 26
#28 5
#29 3
#30 32
#31 2
#32 2
#33 5
#34 44
#35 1
#36 2
#37 1
#38 4
#39 1
#40 29
#41 42
#42 1
#43 1
#44 1
#45 2
#46 6
#47 4
#48 44
#49 1
#50 1
*/
Leave a Comment