singhguru2001
BAN USERThanks!! But I see that you are searching for the element linearly. We could just write a for loop for doing the same rather than going through the pain of recursion. Don't you think so?
- singhguru2001 September 08, 2014If we look at the above code, I see that we will be able to tell if a path exists or not. But we will not be able to tell what points are followed(correct me if I missed something). Using the above, how could we find the points also?
- singhguru2001 September 07, 2014I see that there is recursive algorithm being used. Is there a need to have recursive algorithm? I was able to achieve this with the below code. I agree that there is still a need to optimize the way we check for visited nodes.
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace matrixnxn
{
class Program
{
static int endX = 3, endY = 3;
static int m = 3, n = 4;
static int[,] matrix = new int[,] { { 0, 1, 0, 0, 0 },
//0,0 0,1 0,2 0,3 0,4
{ 0, 0, 1, 0, 0 },
//1,0 1,1 1,2 1,3 1,4
{ 0, 1, 0, 0, 1 },
//2,0 2,1 2,2 2,3 2,4
{ 0, 0, 1, 0, 0 }
//3,0 3,1 3,2 3,3 3,4
};
static void Main(string[] args)
{
int startX=1,StartY=1;
var x=FindPath(startX, StartY, endX, endX);
}
private static Stack<Point> FindPath(int startX, int StartY, int endX1, int endX2)
{
Queue<Stack<Point>> paths = new Queue<Stack<Point>>();
Stack<Point> temp = new Stack<Point>();
temp.Push(new Point() { X = startX, Y = StartY });
paths.Enqueue(temp);
while(paths.Count>0)
{
Stack<Point> currentPoint = paths.Dequeue();
if (currentPoint.Peek().X == endX && currentPoint.Peek().Y == endY)
return currentPoint;
List<Stack<Point>> newPoint = FindPoints(currentPoint);
foreach (var item in newPoint)
paths.Enqueue(item);
}
return null;
}
private static List<Stack<Point>> FindPoints(Stack<Point> currentPoint)
{
Point p = currentPoint.Peek();
List<Stack<Point>> newPoint = new List<Stack<Point>>();
if (p.X - 1 >= 0 && p.Y >= 0 && matrix[p.X-1,p.Y]==0)
{
var list = currentPoint.Where(x => x.X == p.X -1&& x.Y == p.Y).ToList();
if(list.Count==0)
newPoint.Add(StackCopy(currentPoint, p.X - 1, p.Y));
}
if (p.X >= 0 && p.Y - 1 >= 0 && matrix[p.X, p.Y-1] == 0)
{
var list = currentPoint.Where(x => x.X == p.X && x.Y == p.Y-1).ToList();
if (list.Count == 0)
newPoint.Add(StackCopy(currentPoint, p.X, p.Y - 1));
}
if (p.X <= m && p.Y + 1 <= n && matrix[p.X, p.Y+1] == 0)
{
var list = currentPoint.Where(x => x.X == p.X && x.Y == p.Y+1).ToList();
if (list.Count == 0)
newPoint.Add(StackCopy(currentPoint, p.X, p.Y + 1));
}
if (p.X + 1 <= m && p.Y <= n && matrix[p.X+1, p.Y] == 0)
{
var list = currentPoint.Where(x => x.X == p.X +1&& x.Y == p.Y).ToList();
if (list.Count == 0)
newPoint.Add(StackCopy(currentPoint, p.X+1, p.Y));
}
return newPoint;
}
private static Stack<Point> StackCopy(Stack<Point> currentPoint, int p1, int p2)
{
Point[] currentPointArray = new Point[currentPoint.Count];
currentPoint.CopyTo(currentPointArray,0);
Stack<Point> returnStack=new Stack<Point>();
for(int i=currentPointArray.Length-1;i>=0;i--)
returnStack.Push(currentPointArray[i]);
returnStack.Push(new Point() { X = p1, Y = p2 });
return returnStack;
}
}
class Point
{
public int X { get; set; }
public int Y { get; set; }
}
}
Please review and pass feedback.
Yes. There is an issue with the above code if there exists duplicate values. There is another code mentioned below which is tested for duplicates. Please look at it and let me know if you have any questions.
- singhguru2001 September 07, 2014Hmm, it works great!!! The only problem is that it is not returning the positing of the first occurrence of 4. In the above input, it should return 6, but it returns 7. : ( similar issue was with the code I first posted when duplicates existed.
- singhguru2001 September 07, 2014
Hi Shekhar, if you were to look at the matrix, you would find 1s in them. instead of having "x" I have "1" to show that you cannot go through that point.
- singhguru2001 September 08, 2014in FindPoints I am checking if the next move(top, bottom, left, right) is allowed or not.