30pts全输出0求助
  • 板块P1605 迷宫
  • 楼主_caiji_
  • 当前回复5
  • 已保存回复5
  • 发布时间2021/1/6 17:18
  • 上次更新2023/11/5 05:05:51
查看原帖
30pts全输出0求助
390033
_caiji_楼主2021/1/6 17:18
#include <cstdio>
#include <cstring>
using namespace std;
bool qiang[10][10],visit[10][10];
int ans,n,m,t,stx,sty,edx,edy;
const int dbx[4]={-1,0,0,1},
          dby[4]={0,-1,1,0};
void dfs(int x,int y){
    if(x==edx&&y==edy){
        ans++;//到终点回头
        return ;
    }
    if(qiang[x][y]) return ;//有墙就回头
    if(visit[x][y]) return ;//走过了回头
    //visit[stx][sty]=1;
    for(int i=0;i<4;i++){
        int tempx=x+dbx[i],tempy=y+dby[i];
        visit[tempx][tempy]=1;//回溯
        dfs(tempx,tempy);
        visit[tempx][tempy]=0;
    }
}
int main(){
    memset(qiang,1,sizeof(qiang));//1代表是墙
    scanf("%d%d%d",&n,&m,&t);
    scanf("%d%d%d%d",&stx,&sty,&edx,&edy);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            qiang[i][j]=0;//标记能走的地方
    for(int i=0,ix,iy;i<t;i++){
        scanf("%d%d",&ix,&iy);
        qiang[ix][iy]=1;//造墙
    }
    dfs(stx,sty);
    printf("%d",ans);
    return 0;
}
2021/1/6 17:18
加载中...