LeetCode 980. 不同路径 III（DFS+回溯）

class Solution {
    int sx,sy,ex,ey;//起点终点坐标
    int m,n,steps = 0;
    vector<vector<int>> dir = {{-1,0},{1,0},{0,1},{0,-1}};
public:
    int uniquePathsIII(vector<vector<int>>& grid) {
        int i, j;
        m = grid.size(), n = grid[0].size();
        for(i = 0; i < m; ++i)
        	for(j = 0; j < n; ++j)
        	{
        		if(grid[i][j] != -1)
        			steps++;//计算需要走的格子数
        		if(grid[i][j] == 1)
        			sx = i, sy = j;//起点
        		else if(grid[i][j] == 2)
        			ex = i, ey = j;//终点
        	}
		int paths = 0;
		grid[sx][sy] = -1;//起点标记走过了
		dfs(grid, sx, sy, 1, paths);
		return paths;
    }

    void dfs(vector<vector<int>>& grid, int x, int y, int step, int &paths) 
    {
    	if(x == ex && y == ey)//终点
    	{
    		if(step == steps)//走过所有的地方
    			paths++;//方案+1
    		return;
    	}
    	int x0, y0, origin;
    	for(int k = 0; k < 4; ++k)
    	{
    		x0 = x+dir[k][0];
    		y0 = y+dir[k][1];//周围四个方向坐标
    		if(x0 >= 0 && x0 < m && y0 >= 0 && y0 < n && grid[x0][y0] != -1)
    		{	//坐标未出界，且没有访问过
	    		origin = grid[x0][y0];//位置原始信息
    			grid[x0][y0] = -1;//访问过了
    			dfs(grid,x0,y0,step+1,paths);//dfs
    			grid[x0][y0] = origin;//回溯，恢复现场
    		}
    	}
    }
};