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/7eaa82e3-f406-44e3-8b4d-a5a66ac8bc85%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
