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! |
coding hangover 