//處理第index個(gè)盒子 _ - - 并行遞歸，n有多大我們就調(diào)用多少次
DFS(vector<int>& box,int index,vector<int>& visited,int n)
{//box為盒子，index為當(dāng)前盒子，visited為標(biāo)記哪張牌用了的數(shù)組，n為處理幾張牌
	if(index == n+1)//每一個(gè)盒子都有牌了
	{
		return;
	}
	for(int i =1;i<n;++i)
	{
		if(visited[i]==0)
		{
			//表示沒(méi)有用過(guò)的牌就可以放在當(dāng)前的盒子當(dāng)中
			box[index] = i;//當(dāng)前的盒子放這張牌
			visited[i] =1 ;
			//這里的邏輯就是我們站在一個(gè)盒子，我們按照我們手中的牌，從小到大依次嘗試
			//到這里我們就處理下一個(gè)盒子
			DFS(box,index+1,visited,n);
			//一種方法完成，我們就回收牌
			visited[i]=0;//標(biāo)記成0就可以再次使用啦！
		}
	}
}

void DFS(int index, int n, vector<int>& box, vector<int>& visited)
{
	//處理當(dāng)前的盒子

	//我們這里打印看看每個(gè)盒子裝的都是什么
	if (index == n + 1)
	{
		for (int i=1;i<box.size();++i)
			cout << box[i] << " ";
		cout << endl;
		
		//表示每個(gè)盒子我們都已經(jīng)放滿了東西，我們就可以返回上一層
		return;
	}

	//每個(gè)盒子都要用n張牌來(lái)看看是否能夠使用，按照我們從小到大使用的規(guī)定原則
	for (int i = 1; i <= n; ++i)
	{
		//表示牌沒(méi)有被用過(guò)，可以使用
		if (visited[i] == 0)
		{
			box[index] = i;//表示在看到index個(gè)盒子的時(shí)候，我們用第i張牌放入
			
			visited[i] = 1;//標(biāo)記當(dāng)前牌已經(jīng)被使用
			//走到這里我們當(dāng)前這個(gè)盒子該干的事情已經(jīng)干完了，我們就可以處理下一個(gè)盒子

			DFS(index + 1, n, box, visited);
			//表示所有的牌都已經(jīng)放入并且返回，這時(shí)我們回收牌
			visited[i] = 0;
		}
	}
}
int main()
{
	int n;
	vector<int> box;
	vector<int> vistied;
	cin >> n;
	box.resize(n + 1, 0);
	vistied.resize(n + 1, 0);
	//這里的1是我們當(dāng)前走到盒子，n是我們有多少牌，boxs是我們用來(lái)存放的盒子，	
	//visited是用來(lái)確定是否訪問(wèn)過(guò)的標(biāo)記矩陣
	DFS(1, n, box, vistied);
	return 0;
}

/*
// Definition for Employee.
class Employee {
public:
    int id;
    int importance;
    vector<int> subordinates;
};
*/

class Solution {
public:
    int getImportance(vector<Employee*> employees, int id) {
        
    }
};

for(int id: um[id]->subordinates)
        {
            //對(duì)于當(dāng)前我們需要sum加上加上當(dāng)前id的重要度
            sum += um[id]->importance;
            //遍歷當(dāng)前id的所有直系下屬
            DFS(id,um,sum);
        }

// 題目答案:
class Solution {
public: 
    void DFS(int id,unordered_map<int,Employee*>& um,int& sum)
    {
        //對(duì)于每一個(gè)id，下屬的id都會(huì)有屬于他們的vector<int> subordinates;
        //所以我們都要去遍歷當(dāng)前id的subordinates
        for(int id: um[id]->subordinates)
        {
            //對(duì)于當(dāng)前我們需要sum加上加上當(dāng)前id的重要度
            sum += um[id]->importance;
            //遍歷當(dāng)前id的直系下屬(**一路走到黑**),統(tǒng)計(jì)完的結(jié)果放到sum當(dāng)中
            DFS(id,um,sum);
        }
    }
    
    int getImportance(vector<Employee*> employees, int id) {
        //單個(gè)員工 id ，返回這個(gè)員工和他所有下屬的重要度之和。
        //DFS:深度遍歷這個(gè)員工的旗下所有重要度之和，這題適合一條路走到黑
        //因?yàn)樵趘ector中的查找都是O（N）的時(shí)間復(fù)雜度，我們選擇用哈希表，并且將id與員工的指針建立映射,因?yàn)槲覀冊(cè)贒FS中要使用到用id找到員工
        unordered_map<int,Employee*> um;
        for(Employee* e : employees)
        {
            //將employees的數(shù)據(jù)導(dǎo)入us（哈希表中）
            um[e->id] = e;
        }
        int sum = um[id]->importance;//提前加上當(dāng)前id的重要度
        //dfs是遍歷當(dāng)前id的subordinates的重要度
        DFS(id, um,sum);
        return sum;
    }
};

int arr[4][2] ={{1,0},{0,1},{-1,0},{0,-1}};//方向矩陣
    void DFS(vector<vector<int>>& image, int curX, int curY, int newColor,int row ,int col,int oldcolor)
    {
        image[curX][curY] = newColor;//上色
        //遍歷 (sr，sc)的上下左右 -- 我們可以設(shè)置一個(gè)全局的方向矩陣
        for(int i=0;i<4;++i)
        {
            //(newX,newY)就是該點(diǎn)的上下左右了
            int newX = curX+arr[i][0];
            int newY = curY+arr[i][1];
            if(newX<0||newX>=row
            ||newY<0||newY>=col)
            continue;//表示新的坐標(biāo)越界了不符合要求，跳過(guò)
            
            //走到這里表示新的坐標(biāo)沒(méi)有問(wèn)題,如果是就顏色我們就上色
            if(image[newX][newY] == oldcolor)
            {     
                //當(dāng)前的點(diǎn)處理完，我們處理下一個(gè)點(diǎn)
                DFS(image,newX,newY,newColor,row,col,oldcolor);
            }
            else
            continue;        
        }
    }

int arr[4][2] ={ { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
class Solution {
public:
    void DFS(vector<vector<int>>& image, int curX, int curY, int newColor,vector<vector<int>>& visited,int row ,int col,int oldColor)
    {
        //給當(dāng)前位置染色
         image[curX][curY] = newColor;
         //標(biāo)記當(dāng)前位置已經(jīng)使用了
         visited[curX][curY]=1;

        
        //遍歷 (sr，sc)的上右下左 -- 我們可以設(shè)置一個(gè)全局的方向矩陣
        for(int i=0;i<4;++i)
        {
            //(newX,newY)就是該點(diǎn)的上下左右了
            int newX = curX+arr[i][0];
            int newY = curY+arr[i][1];
            //判斷新坐標(biāo)是否合法
            if(newX<0 || newX>=row
            || newY<0 || newY>=col)
            continue;

            
            //如果是沒(méi)有訪問(wèn)過(guò)的并且是舊顏色就遞歸這個(gè)點(diǎn)的周?chē)?
            if(visited[newX][newY] == 0 && 
               image[newX][newY] == oldColor)
                 DFS(image,newX,newY,newColor,visited,row,col,oldColor) ; 
               
        }
    }
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
    //我們這道題也可以用BFS，DFS做都沒(méi)問(wèn)題，我們這里講到DFS，所以就用DFS的思路解決
        int row = image.size();
        int col = image[0].size();
        int oldColor =image[sr][sc];
        //初始化標(biāo)記矩陣，沒(méi)訪問(wèn)過(guò)的置成0
        vector<vector<int>> visited(row,vector<int>(col,0));
        DFS(image,sr,sc,newColor,visited,row,col,oldColor);
        return image;
    }
};

int arr[4][2] ={ { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
class Solution {
public:
    void DFS(vector<vector<char>>& board,int row,int col,int curX,int curY)
    {
        //當(dāng)前點(diǎn)就是聯(lián)通的‘O'
        board[curX][curY] ='#';
        for(int i =0;i<4;++i)
        {
            int newX = curX+arr[i][0];
            int newY = curY+arr[i][1];
            if(newX<0||newX>=row
            ||newY<0||newY>=col)
            continue;
            if(board[newX][newY]=='O')
            DFS(board,row,col,newX,newY);
        }
    }
    void solve(vector<vector<char>>& board) {
        //我們可以從每一個(gè)邊界的O出發(fā)，鏈接的O就是不用改的，其他的都是要改成‘X'的
        //但是我們可以通過(guò)修改與外面相連的O暫時(shí)修改#，就不需要標(biāo)記矩陣了
        int row =board.size();
        int col=board[0].size();
        for(int i=0;i<row;++i)
        {
            if(board[i][0] =='O')
            DFS(board,row,col,i,0);
            if(board[i][col-1] =='O')
            DFS(board,row,col,i,col-1);
        }
        for(int j =0;j<col;++j)
        {
            if(board[0][j]=='O')
            DFS(board,row,col,0,j);
            if(board[row-1][j]=='O')
            DFS(board,row,col,row-1,j);
        }
        for(int i =0;i<row;++i)
        {
            for(int j =0;j<col;++j)
            {
                if(board[i][j]=='O')
                board[i][j]='X';
                if(board[i][j]=='#')
                board[i][j]='O';
            }
        }
        return ;
    }
};

int arr[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
class Solution {
public:
    void DFS(vector<vector<int>>& visited,vector<vector<char>>& board,int row,int col,int curX ,int curY)
    {
        //與外界聯(lián)通的還是O，我們標(biāo)記為1
        visited[curX][curY] = 1;

        for(int i =0;i<4;++i)
        {
            int newx = curX+arr[i][0];
            int newy = curY+arr[i][1];
            if(newx<0||newx>=row||
            newy<0||newy>=col)
            continue;
            //沒(méi)有被訪問(wèn)過(guò)的位置（防止重復(fù)遞歸）&& 為O的位置我們才遞歸
            if(visited[newx][newy]==0&&
            board[newx][newy]=='O')
            {
                DFS(visited,board,row,col,newx,newy);
            }       
        }
    }
    void solve(vector<vector<char>>& board) {
        //思路：我們從周?chē)腛出發(fā)，與邊界O DFS都能獲取到的位置我們都可以做個(gè)標(biāo)記
        //最后將標(biāo)記的不動(dòng)，沒(méi)標(biāo)記的換成'X'(內(nèi)陸)。
        int row = board.size();
        int col=board[0].size();
        vector<vector<int>> visited(row,vector<int>(col,0));
        //遍歷周?chē)鸀镺的位置
        //兩列
        for(int i =0;i<row;++i)
        {
            if(board[i][0]=='O')
            DFS(visited,board,row,col,i,0);
            if(board[i][col-1]=='O')
            DFS(visited,board,row,col,i,col-1);       
        }
        //兩行
        for(int j =0;j<col;++j)
        {
            if(board[0][j]=='O')
            DFS(visited,board,row,col,0,j);
            if(board[row-1][j]=='O')
            DFS(visited,board,row,col,row-1,j);    
        }
        //最后將沒(méi)有標(biāo)記的O換成X，標(biāo)記了的不變
        for(int i =0;i<row;++i)
        {
            for(int j =0;j<col;++j)
            {
                if(visited[i][j]==0)
                board[i][j] = 'X';
                cout<<visited[i][j];
            }
        }
    }
};

int arr[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
class Solution {
public:
    void DFS(vector<vector<int>>& visited,vector<vector<char>>& grid,int row,int col,int curx,int cury)
    {
        //將當(dāng)前位置標(biāo)記為走過(guò)
        visited[curx][cury]=1;
        for(int i =0;i<4;++i)
        {
            int newx = curx+arr[i][0];
            int newy = cury+arr[i][1];
            if(newx<0||newx>=row||newy<0||newy>=col)
                continue;
            if(grid[newx][newy]=='1'&&visited[newx][newy]==0)
            DFS(visited,grid,row,col,newx,newy);
        }
    }
    int numIslands(vector<vector<char>>& grid) {
        //這道題其實(shí)也是用BFS，DFS都可以解，用DFS的話我的思路是從第一個(gè)開(kāi)始遍歷，遇到一個(gè)visited沒(méi)有訪問(wèn)過(guò)的1就去遍歷他的上下左右，將他周?chē)?都遍歷，在將次數(shù)加一
        int row =grid.size();
        int col=grid[0].size();
        int count =0;
        vector<vector<int>> visited(row,vector<int>(col,0));
        for(int i =0;i<row;++i)
        {
            for(int j =0;j<col;++j)
            {
                if(visited[i][j]==0&&grid[i][j]=='1')
                {
                    DFS(visited,grid,row,col,i,j);
                    count++;
                }
            }
        }
        return count;
    }
};