CareerCup

use the dynamic programming state dp[x][y][wall]
where (x,y) are co-ordinates and wall is the number of walls removed
dp[x][y][wall] will store the minimum cost of reaching (x,y) from start position.
suppose u are at position (x,y,wall) .
Now if you move and hit the wall increment wall and store it in the new co-ordinates.

The first one is easily solved by BFS. The second one is easily solved by BFS which can go through a wall up to 3 times.

Try A* search that can go through 3 walls.

public class CMain {

	public static void main(String[] args){
		
	Point p = new Point(0, 0);
	
	p.findPath(new Point(0,0), new Point(5,5), p, new char[10][10]);
	
	}
}

public class Point {

	int x;
	int y;
	
	public Point(int _x,int _y){
		this.x=_x;
		this.y=_y;
	}
	
	public boolean findPath(Point start,Point end,Point current,char[][] map){
		if(
		   current.x<0 || current.y<0 ||
		   current.x >= (map[current.y].length -1 ) ||
		   current.y >= (map.length-1) ||
		   map[current.y][current.x]=='X'
		   )
			return false;
		
		if(current.x==end.x && current.y==end.y){
			System.out.println(current.x +" , "+ current.y);
			return true;
		}
		
		if(current.x<end.x ){
			System.out.println(current.x +" , "+ current.y);
			return findPath(start,end,new Point(current.x+1,current.y),map);
		}
		else if(current.x>end.x ){
			System.out.println(current.x +" , "+ current.y);
			return findPath(start,end,new Point(current.x-1,current.y),map);
		}
		else if (current.y<end.y){
			System.out.println(current.x +" , "+ current.y);
			return findPath(start,end,new Point(current.x,current.y+1),map);
		}
		else if (current.y>end.y){
			System.out.println(current.x +" , "+ current.y);
			return findPath(start,end,new Point(current.x,current.y-1),map);
		}
		else 
			return false;
			
		
	}
	
	
}

Disjktra
Neighbors are connected by regular edges
Blocked neighbors connected by special edges.
Count distance and number of special edges
If distance is the same, less special edges is better.
Don't walk special edges if already took 3.

int arr[100][100]; // will store the map, presently each edge weight is assumed 0 or 1
int m,n;
bool isOk(int a,int b){
	return (a>=0 && a<n && b>=0 && b<m && arr[a][b]!=0);
}

int shortestPath(int startX,int startY,int endX,int endY){
	queue< pair< int,int> > q;
	q.push(mp(startX,startY));
	int dis=[0,0,1,-1];
	int disY =[1,-1,0,0];
	int dist[100][100];
	rep(i,n)
		rep(j,m)
			dist[i][j]=mod;
	dist[startX][startY]=0;
	while(!q.empty()){
		startX = q.top().first;
		startY= q.top().second;
                q.pop();
		rep(i,4){
			a = startX+dis[i];
			b = startY +disY[i];
			if(isOk(a,b) && dist[a][b] > dist[startX][startY]+1)
			{
				dist[a][b] = dist[startX][startY];
				q.push(mp(a,b));
			}

		}
	}
	return dist[endX][endY];
}

#include <queue>
#include <vector>
#include <iostream>
using namespace std;

struct Tuple4 {
  int dis, x, y, wall;
};

inline bool operator< (const Tuple4& lhs, const Tuple4& rhs){
    if(lhs.dis != rhs.dis) return lhs.dis > rhs.dis;
    else return lhs.wall < rhs.wall;
}

vector<pair<int, int>> solve(vector<vector<int>> maze, int sx, int sy, int dx, int dy, int w) {
  int n = maze.size(), m = maze[0].size();
  bool visited[n][m][w + 1];
  int dis[n][m][w + 1];
  int min_dis[n][m], prev[n][m][2];
  for(int i = 0; i < n; i ++)
    for(int j = 0; j < m; j ++) {
      min_dis[i][j] = INT_MAX;
      prev[i][j][0] = prev[i][j][1] = -1;
      for(int k = 0; k <= w; k ++) {
        visited[i][j][k] = false;
        dis[i][j][k] = INT_MAX;
      }
    }

  priority_queue<Tuple4> pq;
  pq.push(Tuple4{0, sx, sy, w});
  dis[sx][sy][w] = 0;
  min_dis[sx][sy] = 0;
  int ddx[] = {0, 0, -1, 1};
  int ddy[] = {-1, 1, 0, 0};
  while(!pq.empty()) {
    Tuple4 node = pq.top();
    pq.pop();
    visited[node.x][node.y][node.wall] = true;
    if(node.x == dx && node.y == dy) break;
    for(int i = 0; i < 4; i ++) {
      int nx = node.x + ddx[i];
      int ny = node.y + ddy[i];
      if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
      else if(maze[nx][ny] == 0) { // not wall
        if(visited[nx][ny][node.wall])
          continue;
        else {
          if(dis[nx][ny][node.wall] <= node.dis + 1) continue;
          dis[nx][ny][node.wall] = node.dis + 1;
          pq.push(Tuple4{node.dis + 1, nx, ny, node.wall});
          if(dis[nx][ny][node.wall] < min_dis[nx][ny]) {
            min_dis[nx][ny] = dis[nx][ny][node.wall];
            prev[nx][ny][0] = node.x, prev[nx][ny][1] = node.y;
            cout << nx << "," << ny << " : " << node.x << "," << node.y << endl;
          }
        }
      } else { // wall
        if(node.wall == 0) continue;
        else if(visited[nx][ny][node.wall-1]) continue;
        else {
          if(dis[nx][ny][node.wall - 1] <= node.dis + 1) continue;
          dis[nx][ny][node.wall - 1] = node.dis + 1;
          pq.push(Tuple4{node.dis + 1, nx, ny, node.wall - 1});
          if(dis[nx][ny][node.wall - 1] < min_dis[nx][ny]) {
            min_dis[nx][ny] = dis[nx][ny][node.wall - 1];
            prev[nx][ny][0] = node.x, prev[nx][ny][1] = node.y;
            cout << nx << "," << ny << " : " << node.x << "," << node.y << endl;
          }
        }
      }
    }
  }
  vector<pair<int, int>> ret;
  do {
    ret.push_back(make_pair(dx, dy));
    int tdx = prev[dx][dy][0];
    int tdy = prev[dx][dy][1];
    dx = tdx, dy = tdy;
  } while(dx != -1 && dy != -1);
  return ret;
}

int main() {
  vector<vector<int>> maze = {
    {0, 1, 1, 1, 1, 0},
    {0, 1, 1, 0, 1, 0},
    {0, 0, 1, 0, 0, 0},
    {0, 1, 0, 0, 0, 1},
    {0, 0, 0, 1, 0, 0}
  };

  vector<pair<int, int>> ans = solve(maze, 0, 0, 0, 5, 3);
  for(auto n : ans) {
    cout << n.first << " " << n.second << endl;
  }
  return 0;
}

Adapted from Dijkstra

#include <vector>
using namespace std;

enum GridOrientation
{
	GRID_LEFT,
	GRID_RIGHT,
	GRID_UP,
	GRID_DOWN
};

class PosLoc
{
public:
	PosLoc( vector<int> &path, int Loc )
	{
		_Path = path;
		_Loc = Loc;
	}

	PosLoc &operator=(const PosLoc &cLoc)
	{
		_Path = cLoc._Path;
		_Loc = cLoc._Loc;
		return *this;
	}

	vector<int> _Path;
	int _Loc;
};

// this is assuming the array is fixed size
int GetPos( GridOrientation eGO, int nPos )
{
	int nRet = -1;

	// calculates the location based on the fix grid size if its a 10x10, easy calculations
	switch (eGO)
	{
		case GRID_LEFT:
		case GRID_RIGHT:
		case GRID_UP:
		case GRID_DOWN:
		default:
			break;
	}

	return nRet;
}

bool NotInSearch( vector<int> &vSearch, int nPos )
{
	for(int i = 0; i < vSearch.size(); i++)
	{
		if ( vSearch[i] == nPos )
			return true;
	}

	return false;
}

/*
	Parameters:
		gird[] - an array 0 ... N-1 (assuming 10x10) of bool (no wall=FALSE, wall=TRUE)
		start - starting position
		target - target position

	Returns:
		a vector of the path not including the target
*/
vector<int> FindShortestPath( bool grid[100], int start, int target )
{
	vector<int> vShortest;
	vector<PosLoc> vSearch;

	// starting location
	vSearch.push_back( PosLoc(sShortest,start) );
	
	while( vSearch.size() > 0 )
	{
		PosLoc posCurrent = vSearch.back(); vSearch.pop_back();

		if ( posCurrent._Loc == target )
		{
			// is this path better than the last path?
			if ( posCurrent._Path.size() < sShortest.size() || sShortest.size() == 0 )
			{
				vShortest.empty();
				vShortest = posCurrent._Path;
			}
		}
		else
		{
			vector<int> currentPath = posCurrent._Path;

			currentPath.push_back(posCurrent._Loc);

			// four possible directions, but can't overlap ones that we've been to before
			for(int e = GRID_LEFT; e <= GRID_DOWN; e++ )
			{
				int nPos = GetPos( (GridOrientation)e, posCurrent._Loc );

				if ( nPos != -1 &&	// is a valid location
					grid[nPos] != true && // is a wall?
					NotInSearch( sShortest, nPos )	// have not searched in the path before
					)
				{
					// this is a possible path
					vSearch.push_back(PosLoc(currentPath, nPos));
				}
			}
		}
	}

	return vShortest;
}

Do a DFS without considering the walls from source to destination but keep the count of walls you have already passed through. When you get to the destination, see if you have passed through at most 3 walls. If so, use that path as a solution, compare it to the global min path and update the min if possible. To optimize, your DFS should backtrack as soon as it hits the 4th wall.

test

Solve it like Ford-Bellman, suppose n is n_rows, m is n_cols

int A[n][m][4];

//initialize all cells in A to be INF, except the A[original_row][original_col] = 0

//loop maximum 3 walls, generally can have many walls as you want
//we can separate to handle with 0-wall case by BFS and run this below code with k-wall. However, we can also combine all of them in the same code. The complexity won't be differed anyway. Each loop in k, this will perform Ford-Bellman algorithm, which has O(|V|*|E|) = O(n*n*m*m). Overall, this code will have O(k*n*n*m*m).

for(int k=0;k<=3;k++){
  while(true){
    bool update = false;
    for(int i=0;i<n;i++)
      for(int j=0;j<m;j++){
        //two cases
        if(k==0) {
           //k = 0 we are dealing with not removing any wall
           if(!wall[i][j]){
             int min_val = min(A[i-1][j],A[i][j-1],A[i+1][j],A[i][j+1])+1
             if(A[i][j] > min_val){
               A[i]j[j] = min_val
               update =true
             }
           }
        }
        else{
          if(!wall[i][j){
            //same as below case, because this is not a wall, we cannot remove this wall. So the optimal result for this cell must the optimal value when we reserve the same number of walls (k walls) for neighbors
            int min_val = min(A[i-1][j][k],A[i+1][j][k],A[i][j-1][k],A[i][j+1][k])+1;
            if(A[i][j][k] > min_val){
              A[i][j][k] = min_val;
              update = true;
            }
          }
        else{
         //this is a wall, we must remove it. So we apply the k-1 walls to our neighbors to find out the optimal value then update this current cell
          int min_val = min(A[i-1][j][k-1],A[i+1][j][k-1],A[i][j-1][k-1],A[i][+1][k-1])+1
            if(A[i][j][k] >min_val ){
              A[i][j][k] = min_val;
              update = true;
            }
        }
      }
    //we got an optimal update of the grid for a maximum k walls, let consider to deal with k+1 walls
    if(!update)
      break;
  }
}

//The result stores at A[dest_row][des_col][3];

We can separate to handle with 0-wall case by BFS and run this above code with k-wall. However, we can also combine all of them in the same code. The complexity won't be differed anyway. Each loop in k, this will perform Ford-Bellman algorithm, which has O(|V|*|E|) = O(n*n*m*m). Overall, this code will have O(k*n*n*m*m). We can call this algorithm is DP with Ford-Bellman. DP is for reusing the optimal value with previous number of walls and Ford Bellman is for continuing updating the grid in the same number of walls