For the problem Parcels in this round, can someone tell me why I'm still getting wrong answer?
My solution is firstly doing BFS from the squares with value 1, then doing binary search for the target distance. Within the binary search, I loop through the squares. If the original distance of the square (i,j) is greater than the assumed distance, I pick the square to see its i+j and i-j value. After checking all squares, if max(i+j)-min(i+j)<=2*dist and max(i-j)-min(i-j)<=2*dist, then I judge the distance dist achievable. My code is as following: #include<bits/stdc++.h> using namespace std; int main(){ int dx[4] = {0,0,1,-1},dy[4] = {1,-1,0,0}; int tt;cin>>tt; for(int t=1;t<=tt;t++){ int r,c;cin>>r>>c; vector<string> initial; for(int i=0;i<r;i++){ string row;cin>>row; initial.push_back(row); } vector<vector<int> > dist; queue<pair<int,int> > q; for(int i=0;i<r;i++){ vector<int> row; for(int j=0;j<c;j++){ if(initial[i][j]=='1'){ row.push_back(0); q.push(make_pair(i,j)); }else row.push_back(INT_MAX); } dist.push_back(row); } int max_dist=0; while(!q.empty()){ int x = q.front().first,y = q.front().second; q.pop(); max_dist = max(max_dist,dist[x][y]); for(int i=0;i<4;i++){ int xx = x+dx[i],yy = y+dy[i]; if(xx>=0 && xx<r && yy>=0 && yy<c){ if(dist[xx][yy]>dist[x][y]+1){ dist[xx][yy] = dist[x][y]+1; q.push(make_pair(xx,yy)); } } } } int lower=-1,upper=max_dist; while(upper-lower>1){ int mid = (upper+lower)/2; int ipjmax=-r-c-1,ipjmin=r+c+1,imjmax=-r-c-1,imjmin=r+c+1; for(int i=0;i<r;i++){ for(int j=0;j<c;j++){ if(dist[i][j]>mid){ ipjmin = min(i+j,ipjmin); ipjmax = max(i+j,ipjmax); imjmin = min(i-j,imjmin); imjmax = max(i-j,imjmax); } } } if(((ipjmax-ipjmin)<=2*mid) && ((imjmax-imjmin)<=2*mid))upper = mid; else lower = mid; } cout<<"Case #"<<t<<": "<<upper<<endl; } return 0; } -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/7eaa82e3-f406-44e3-8b4d-a5a66ac8bc85%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.