问题标题: 酷町堂：4960 50分 救助

题目链接： 酷町堂：4960

4960   古墓猫影

经验值：1600 时间限制：1000毫秒 内存限制：128MB

题目描述 Description

酷町猫在玩古墓丽影这款游戏，现在她拿到了一个藏宝图。在一个m×n密室中，布满了重重陷阱。密室的入口用2标记，出口用3表示，陷阱用-1表示。其余位置都是可以通行的房间。在这些房间里，有的放着宝物。放着宝物的房间用1表示，没有放宝物的房间用0表示。现在酷町猫想让你帮忙看看，她能不能从起点顺利到达终点，并且使得每一个放宝物的房间都能经过一次！
一个房间只能被经过一次，一旦经过了就会永远被关闭。一个房间和周围的四个房间相连。

输入描述 Input Description

第一行，两个正整数，m n
接下来m行，每行n个由空格隔开的正整数，为-1到3中的某一个

输出描述 Output Description

如果能够到达，输出yes，否则输出no

样例输入 Sample Input

4 4 2 0 -1 -1 -1 1 0 -1 -1 -1 1 0 -1 -1 -1 3

样例输出 Sample Output

yes

数据范围及提示 Data Size & Hint

m, n<=20

 

#include<iostream>
using namespace std;
int m,n,g[25][25],a1,b1,x,y,vis[25][25],cnt,ans;
int dir[9][9]={{0},{1,0},{0,1},{0,-1},{-1,0}};
bool f;
void dfs(int A,int B)
{
    
    if(A==x&&B==y)
    {
        if(ans==cnt)
        { 
            f=true;
            return ;
        }
    }
    for(int i=1;i<=4;i++)
    {
        int ax=dir[i][0]+A,bx=dir[i][1]+B;
        if(ax>=1&&ax<=m&&bx>=1&&bx<=n&&!(g[ax][bx]==-1)&&!vis[ax][bx])
        {
            vis[ax][bx]=true;
            if(g[ax][bx]==1) ans++;
            dfs(ax,bx);
            if(g[ax][bx]==1) ans--;
        }
    }
}
int main()
{
    cin>>m>>n;
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>g[i][j];
            if(g[i][j]==1) cnt++;
            if(g[i][j]==2) a1=i,b1=j;
            if(g[i][j]==3) x=i,y=j;
        }
    }
    vis[a1][b1]=true;
    dfs(a1,b1);
    if(f==true) cout<<"yes";
    else cout<<"no";
    return 0;
}