Link – http://community.topcoder.com/stat?c=problem_statement&pm=13628&rd=16278
Well, this is a simple graph problem once you get the logic !
A simple BFS traversal is enough to find the maximum x coordinate value.
A visited array is maintained to log the coordinates that are visited (inorder to avoid visiting the same point again)
First of all since John can move in any directions , he can end up in in negative coordinates also. So to represent negative coordinates as array index move origin(0,0) to (1000,1000).(transformation of coordinates. x=x+1000, y=y+1000)
On each traversal compare the x coordinate with current ans and updated it if x Value>ans
On returning the maximum x coordinate dont forget to decrement it with 1000 (inverse transformation of coordinates)
#include <vector> | |
#include <list> | |
#include <map> | |
#include <set> | |
#include <queue> | |
#include <deque> | |
#include <stack> | |
#include <bitset> | |
#include <algorithm> | |
#include <functional> | |
#include <numeric> | |
#include <utility> | |
#include <sstream> | |
#include <iostream> | |
#include <iomanip> | |
#include <cstdio> | |
#include <cmath> | |
#include <cstdlib> | |
#include <ctime> | |
#include <cstring> | |
using namespace std; | |
class TheGridDivTwo { | |
public: | |
typedef struct point{ | |
int x; | |
int y; | |
int k; | |
}point; | |
int valid(int x,int y){ | |
return (x>=0)&&(y>=0)&&(x<=2002)&&(y<=2002); | |
} | |
int find(vector <int> x, vector <int> y, int k) { | |
int visited[2002][2002]; | |
queue<point>q; | |
memset(visited,0,sizeof visited); | |
point origin; | |
origin.x=1000; | |
origin.y=1000; | |
origin.k=k; | |
q.push(origin); | |
visited[1000][1000]=1; | |
for(int i=0;i<x.size();i++){ | |
visited[1000+x[i]][1000+y[i]]=1; | |
} | |
int ans=1000; | |
while(!q.empty()){ | |
point temp=q.front(); | |
point temp1; | |
q.pop(); | |
if(temp.k<=0) | |
continue; | |
if(valid(temp.x+1,temp.y)&&(!visited[temp.x+1][temp.y])){ | |
visited[temp.x+1][temp.y]=1; | |
ans=max(ans,temp.x+1); | |
temp1.x=temp.x+1; | |
temp1.y=temp.y; | |
temp1.k=temp.k-1; | |
q.push(temp1); | |
} | |
if(valid(temp.x-1,temp.y)&&(!visited[temp.x-1][temp.y])){ | |
visited[temp.x-1][temp.y]=1; | |
temp1.x=temp.x-1; | |
temp1.y=temp.y; | |
temp1.k=temp.k-1; | |
q.push(temp1); | |
} | |
if(valid(temp.x,temp.y+1)&&(!visited[temp.x][temp.y+1])){ | |
visited[temp.x][temp.y+1]=1; | |
temp1.x=temp.x; | |
temp1.y=temp.y+1; | |
temp1.k=temp.k-1; | |
q.push(temp1); | |
} | |
if(valid(temp.x,temp.y-1)&&(!visited[temp.x][temp.y-1])){ | |
visited[temp.x][temp.y-1]=1; | |
temp1.x=temp.x; | |
temp1.y=temp.y-1; | |
temp1.k=temp.k-1; | |
q.push(temp1); | |
} | |
} | |
return ans-1000; | |
} | |
}; | |
<%:testing-code%> | |
//Powered by KawigiEdit 2.1.4 (beta) modified by pivanof! |