链接：https://ac.nowcoder.com/acm/problem/17872
来源：牛客网

题目描述

今天是阳光明媚，晴空万里的一天，CSL早早就高兴地起床走出寝室到校园里转悠。

但是，等到他回来的时候，发现他的校园卡不见了，于是他需要走遍校园寻找它的校园卡。CSL想要尽快地找回他掉的校园卡，于是便求助于OneDay帮他一起找。

OneDay和CSL在同一已知的地点出发，并以相同的速度（1格/秒）搜索校园，试求两人走遍校园的最短时间。

输入描述: 

第一行为两个整数n,m(1 ≤ n, m ≤ 4)，表示地图的大小。接下来是n行m列的地图：X表示障碍物，S表示起点，O表示空地。障碍物不能直接经过，数据保证所有空地是可达的，起点有且只有一个。

输出描述: 

输出一个整数表示两人共同走遍校园所需的最少时间。

思路（新手，勿喷qwq）

题目要求最少时间，再看看数据范围：4*4，一开始可能会考虑BFS，但是再仔细看看题目，题目要求的是遍历一遍校园中的所有空地，所以应该用DFS来做；
所以考虑用DFS遍历
DFS遍历：直接套模板即可
再看看题目条件，是两个人遍历
可能有的人会想，直接用O的个数/2，如果O的个数是奇数就再+1不就行了？
错误的，举例
SOOO
这种情况答案是3
所以可以考虑一下其他方法
我的想法是：开一个三维的vis数组[2][6][6]，其中[0][][]记录一个人走过的路径，[1][][]记录另一个人走过的路径
那么怎么判断所有的O都被走过了呢？
很简单，只需要遍历一遍整个图，如果图中存在vis[0][][]与vis[1][][]都未为1（即都未走过的点），并且这个点不是X就行啦
至于如何DFS，我的想法是对所有可能的答案都做一遍DFS
所有可能的答案：指先计算出图中O的个数，记作cnt，那么可以知道，答案的范围一定在((cnt+1)/2)~cnt之间
至于怎么实现的，还是看代码吧，里面有注释，应该比较好懂了(DFS不要忘记回溯)

代码如下（含注释）
#include<bits/stdc++.h>
using namespace std;
char mp[6][6];
int vis[2][6][6];
int dir[4][2]= {{1,0},{0,-1},{0,1},{-1,0}}; //方向数组
int n,m,tmp,cnt=0,flag=0,xx,yy,lx;
void DFS(int lx,int x,int y,int num) { //lx:lx=0指第1个人遍历，lx=1指第2个人遍历，x,y:当前坐标，num:需要步数的剩余值
    if(flag) return;
    if(num==0) { //如果已经达到了要求的的值
        if(lx==0) {
            DFS(1,xx,yy,tmp); //如果当前是第1个人，那么切换到第2个人
            return;
        } else {
            int flag2=0;
            for(int i=0; i<n; i++) {
                for(int j=0; j<m; j++) {
                    if(!vis[0][i][j] && !vis[1][i][j] && mp[i][j]!='X') { //判断图中的O点是否已经被两个人中的至少一个人遍历过了
                        flag2=1;
                        break;
                    }
                }
                if(flag2) break;
            }
            if(!flag2) { //如果前面的判断成立，说明O点已经被遍历完了，这个答案有效，同时因为题目要求最小值，所以答案就是这个tmp，直接输出即可
                flag=1;
                printf("%d\n",tmp);
            }
            return;
        }
    }
    for(int i=0; i<4; i++) { //四个方向遍历
        int xt=x+dir[i][0];
        int yt=y+dir[i][1];
        if(xt<0 || yt<0 || xt>=n || yt>=m || mp[xt][yt]=='X') continue;
        vis[lx][xt][yt]++; //这里不能写成vis[][][]=1，因为主函数里面没用memset函数清空每一次查询的vis数组，所以为了保证S位置的标记一直在，需要用回溯和vis[][][]++和vis[][][]--
        DFS(lx,xt,yt,num-1); //同一个人继续遍历
        vis[lx][xt][yt]--; //回溯，这里不能写成vis[][][]=0，理由同上
    }
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=0; i<n; i++) {
        scanf("%s",mp[i]);
    }
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            if(mp[i][j]=='O') { //记录O点的个数
                cnt++;
            }
            if(mp[i][j]=='S') { //标记一下S的位置
                xx=i;
                yy=j;
                vis[0][i][j]=1;
                vis[1][i][j]=1;
            }
        }
    }
    int st=(cnt+1)/2,ed=cnt; //计算答案存在的范围
    for(int i=st; i<=ed; i++) { //遍历所有可能的值，得出结果
        tmp=i;
        DFS(0,xx,yy,tmp);
        if(flag) break;
    }
    return 0;
}