More explanation here. Let's look at a delivery office with distance 1,
it will cover the following map 010 111 010 you can notice that the max(i+j) and max(i-j) will have the same odd/even property no matter how you place this office in the map. On the other hand, 00 00 cannot be covered by a new office with distance 1, no matter where you put the new office at. But the max(i+j) - min(i+j) == 2 and max(i-j) - min(i-j) == 2 This is a good example of a false positive. It is also easy to verify that max(i+j) and max(i-j) should be one odd, one even. They can't be both even or odd. 在 2019年4月2日星期二 UTC-7下午5:00:21，Xiongqi ZHANG写道： > FYI. https://ideone.com/7xQxtR here is a copy of your code (modified) passing > the test. > > 在 2019年4月2日星期二 UTC-7下午4:55:36，Xiongqi ZHANG写道： > > Your solution couldn't handle this case correctly. > > > > 1 > > 4 4 > > 1001 > > 0000 > > 0000 > > 1001 > > > > Your statement > > > 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. > > is not correct. > > > > The correct statement should be > > > > this distance is achievable if > > 1. max(i + j) - min(i + j) < 2 * dist and max(i - j) - min(i - j) <= 2 * > > dist > > or > > 2. max(i + j) - min(i + j) <= 2 * dist and max(i - j) - min(i - j) < 2 * > > dist > > or > > 3. max(i + j) - min(i + j) == 2 * dist and max(i - j) - min(i - j) == 2 * > > dist and max(i + j) + max(i - j) is even. > > > > > > > > 在 2019年4月2日星期二 UTC-7下午3:22:46，Yupeng Gu写道： > > > 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/82779dc7-a6ca-471a-be24-ee348d6f9c1d%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
