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 [email protected].
To post to this group, send email to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/2572d88a-d971-4c20-9c7c-fb4514192ce9%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
