onurtekdas
BAN USERI think the solution depends on the requirements. If the user going to make multiple queries then it is better to construct a data structure. So that each query can be executed in constant time. My algorithm as follows:
1-) Find each connected component (as a set)
2-) Use a hashmap from each node to its connected set
Here is the code:
public class ReachableMaze{
private boolean [][]maze;
private boolean [][]explored;
private Point size;
private HashMap<Point,HashSet<Point>> map;
ReachableMaze(boolean [][]maze){
assert maze != null && maze[0] != null;
size = new Point(maze.length,maze[0].length);
this.maze = maze.clone();
explored = new boolean[size.y][size.x];
map = new HashMap<Point,HashSet<Point>>();
constructMap();
}
public boolean isReachable(Point a, Point b){
if(map.containsKey(a)){
if(map.get(a).contains(b))
return true;
}
return false;
}
private void addNewNode(Queue<Point> q, HashSet<Point> s, int x, int y){
Point newPoint = new Point(x,y);
q.offer(newPoint);
s.add(newPoint);
explored[y][x] = true;
}
private void constructMap(){
for(int i = 0; i < size.y; i++){
for(int j = 0; j < size.x; j++){
//explore the next connected component
if(!maze[i][j] && !explored[i][j]){
Queue<Point> q = new LinkedList<Point>();
HashSet<Point> s = new HashSet<Point>();
addNewNode(q,s,j,i);
while(!q.isEmpty()){
Point curr = q.poll();
int x = curr.x;
int y = curr.y;
if(y < size.y - 1 && !maze[y+1][x] && !explored[y+1][x])
addNewNode(q,s,x,y+1);
if(y > 0 && !maze[y-1][x] && !explored[y-1][x])
addNewNode(q,s,x,y-1);
if(x < size.x - 1 && !maze[y][x+1] && !explored[y][x+1])
addNewNode(q,s,x+1,y);
if(x > 0 && !maze[y][x-1] && !explored[y][x-1])
addNewNode(q,s,x-1,y);
}
//each point in the connected component is connected to the other
for(Point each:s){
map.put(each,s);
}
}
}
}
}
}
I think using an iterative approach could be a better solution for this problem. Here is an alternative algorithm to @Anonymous on October 14, 2010 with O(n) complexity.
1-) create a board (b) and temporary board (t) of size 8x8
2-) set b[y][x] = 1;
3-) for i=1:n
+ initialize t
+ for each index (x,y) set t[y+2][x+1] += 1/8*b[y][x] (similarly for all other moves)
+ set b to t
4-) sum the probs in b and return
Here is the code and a simulator to test the result
#include<iostream>
#include<cstring>
#include<cassert>
#include<cstdlib>
using namespace std;
typedef unsigned int uint;
float probAfterN(uint n, uint x0, uint y0){
assert(x0<8 && y0<8);//assure that initial location is inside the boundaries
float b[12][12],t[12][12];//keep a board of size [12][12] to include outside
//of boundaries so that we get rid of additional if statements
memset(&b[0][0],0,12*12*sizeof(float));
b[y0+2][x0+2] = 1; //(0,0) is the left top corner of the board
for(uint i = 0; i < n; i++){
memset(&t[0][0],0,12*12*sizeof(float));
for(uint y = 2; y <= 9; y++){
for(uint x = 2; x <= 9; x++){
if(b[y][x]>0){
t[y+2][x+1] += 1.0/8.0*b[y][x];
t[y+2][x-1] += 1.0/8.0*b[y][x];
t[y+1][x+2] += 1.0/8.0*b[y][x];
t[y+1][x-2] += 1.0/8.0*b[y][x];
t[y-1][x+2] += 1.0/8.0*b[y][x];
t[y-1][x-2] += 1.0/8.0*b[y][x];
t[y-2][x+1] += 1.0/8.0*b[y][x];
t[y-2][x-1] += 1.0/8.0*b[y][x];
}
}
}
memcpy(&b[0][0],&t[0][0],12*12*sizeof(float));
}
float p = 0;
for(uint y = 2; y <= 9; y++){
for(uint x = 2; x <= 9; x++){
p += b[y][x];
}
}
return p;
}
float simAfterN(uint n, uint x0, uint y0){
assert(x0<8 && y0<8);
uint simNum = 10000, in = 0, x, y;
bool out;
for(int j = 0; j < simNum; j++){
out = false;
x = x0, y = y0;
for(uint i = 0; i < n; i++){
int c = rand()%8;
switch(c){
case 0: y += 2; x += 1; break;
case 1: y += 2; x -= 1; break;
case 2: y += 1; x += 2; break;
case 3: y += 1; x -= 2; break;
case 4: y -= 1; x += 2; break;
case 5: y -= 1; x -= 2; break;
case 6: y -= 2; x += 1; break;
case 7: y -= 2; x -= 1; break;
default: break;
}
if(x >= 8 || y >= 8){
out = true;
break;
}
}
if(!out) in++;
}
return (float)in/simNum;
}
int main(int argc, char **argv){
assert(argc==4);
cout<<probAfterN(atoi(argv[1]),atoi(argv[2]),atoi(argv[3]))<<endl;
cout<<simAfterN(atoi(argv[1]),atoi(argv[2]),atoi(argv[3]))<<endl;
return 0;
}
It does not say that values are positive. This approach does not work for the following case:
sum = 1
4
/\
-1 3
/\
-2 0
1-) Create a bitmap vector where each bit corresponds to an ID. Assuming number of IDs is less than 2^29~(number of bits in 64 MB)
2-) Read backwards as UB_Green suggested
3-) Set the bit corresponding to the current ID
4-) Repeat until previous day
5-) Go through the bit map print the ID's whose bit is set
Complexity O(n) where n is the number of entries.
it would be faster if you get rid of the pow function for example:
f=1, d=1;
for i=1:n
d *= x/i;
f += d;
end
Repcardiroy, Backend Developer at Accolite software
Hi,I am from Taxes, USA. Enthusiastic multilingual translator with years involvement with Spanish-English translations.Looking to additionally improve interpretation ...
Repannehbell8, Quality Assurance Engineer at Globaltech Research
Build and maintain relationships with convention vendors. Resolve issues throughout meeting event timelines.Plan room layouts and event programs, schedule ...
It would be easier to think this way: an item in the minQ is either inserted once or inserted and deleted once. Since an item will not be processed more than 2 times total complexity of the operations on minQ is O(n). Hence the average complexity of the operation is O(1).
- onurtekdas February 01, 2011