【寒假坚持学习鸭】2.1日（暴力dfs）

题目地址：3rd_Practice_A:Illusive Chase
题目大意：先给你一幅图，0表示可以走，1表示障碍物。在第1s的时候，向R（右）走1_{2步，第2s的时候，向D(下)方向走1}2步，第3s的时候向右走一步。问有多少个起始点满足要求。

tag：对每个点来遍DFS

note：二维数组中的xy容易搞混，，，
up和down的加减容易搞混
前几次提交中忽略了i=1~a的过程中碰到障碍的情况

通过此题更加理解DFS、回溯法、边界
此题的核心语句：if(dfs(cx,cy,step+1)) return 1
AC代码：

#include <iostream>
#include <cstdio>
using namespace std;
int m, n, p;
int mp[105][105];
int dir[4][2]={
   {
   -1,0},{
   0,1},{
   1,0},{
   0,-1}};
int cnt;
struct node
{
   
    int a;
    int b;
    int val;
}nod[10005];

int dfs(int x,int y,int step) {
   
    if (x<0||x>=m||y<0||y>=n||mp[x][y]==1)
        return 0;
    if(step == p + 1) return 1;
    int a = nod[step].a;
    int b = nod[step].b;
    int dd = nod[step].val;
    int cx,cy;
    for(int i = 1; i < a; i++) {
   
        cx=x+dir[dd][0]*i;cy=y+dir[dd][1]*i;
        if(mp[cx][cy]) return 0;
    }
    for(int i = a; i <= b; i++)
    {
   
        cx=x+dir[dd][0]*i;cy=y+dir[dd][1]*i;
        if(cx<0||cx>=m||cy<0||cy>=n) break;
        if(mp[cx][cy]) break;
        if(dfs(cx,cy,step+1)) return 1;//*核心*
    }
    return 0;
}

int main() {
   
    int t;
    scanf("%d", &t);
    while(t--) {
   
        cnt = 0;
        p = 0;
        scanf("%d %d",&m, &n);
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                scanf("%d", &mp[i][j]);
        int a, b;
        char c;
        while(scanf("%d%d",&a,&b)==2&&(a+b)) {
   
            getchar();
            c = getchar();
            nod[++p].a = a;
            nod[p].b = b;
            if(c=='U') nod[p].val=0;
            else if(c=='D') nod[p].val=2;
            else if(c=='L') nod[p].val=3;
            else if(c=='R') nod[p].val=1;
        }
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++) {
   
                if(!mp[i][j]&&dfs(i,j,1)) {
   
                    cnt++;
                }
            }
        printf("%d\n", cnt);

    }
    return 0;
}