问题标题: 酷町堂：4960 古墓猫影

4960   古墓猫影

经验值：1600 时间限制：1000毫秒

题目描述 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

80分：

#include<iostream>
using namespace std;
int m,n,a[25][25],a1,b1,x,y,b[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&&!(a[ax][bx]==-1)&&!b[ax][bx]){
            b[ax][bx]=true;
            if(a[ax][bx]==1)ans++;
            dfs(ax,bx);
        }
    }
}
int main(){
    cin>>m>>n;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
            if(a[i][j]==1)cnt++;    
            if(a[i][j]==2)a1=i,b1=j;
            if(a[i][j]==3)x=i,y=j;
        }
    }
    b[a1][b1]=true;
    dfs(1,1);
    if(f==true)cout<<"yes";
    else cout<<"no";
    return 0;
}