bfs无法退出循环

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e3+10;
int n,m,s;
ll k;
ll g[N][N];
int book[N][N]; 
struct Node{
	int x,y;
	ll val;
};
int dx[]={0,1,0};
int dy[]={-1,0,1};
ll bfs(int sx,int sy){
	memset(book,0,sizeof(book));
	queue<Node> q;
	q.push({sx,sy,g[sx][sy]+s});

	book[sx][sy]=1;
	ll ans=-1e18;
	while(q.size()){
		Node now=q.front();
		q.pop();
		if(now.val<0)continue;
		if(now.x==n){
//			cout << sx << " " << sy << endl;
			ans=max(ans,now.val);
//			cout << now.x << " " << now.y << endl;
//			cout << ans << endl;
//			getchar();
			continue;
		}
		for(int i=0;i<3;i++){
			int nx=now.x+dx[i],ny=now.y+dy[i];
			if(nx>n||ny>m||nx<1||ny<1)continue;
			if(now.val+g[nx][ny]<0){
				book[nx][ny]=1;
				continue;
			}
			if(book[nx][ny]&&now.val+g[nx][ny]>k)continue;
			book[nx][ny]=1;
			q.push({nx,ny,min(now.val+g[nx][ny],k)});
//			cout << nx <<" " << ny << " " << now.val+g[nx][ny] << endl;
		}
//		cout << endl;
	}
	return ans;
}
int main(){
	int c,T;
	cin >> c >> T;
	while(T--){
		cin >> n >> m >> s >> k;
//		cout << endl;
		memset(g,0,sizeof(g));
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				cin >> g[i][j];
			}
		}
		ll maxn=-1e18;
		for(int i=1;i<=m;i++){
			maxn=max(bfs(1,i),maxn);
		}
		cout << (maxn<0?-1:maxn) << endl;
	}
    return 0;
}