迷宫[洛谷 P1605]

题目
题目背景

给定一个N*M方格的迷宫，迷宫里有T处障碍，障碍处不可通过。给定起点坐标和终点坐标，问: 每个方格最多经过1次，有多少种从起点坐标到终点坐标的方案。在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。

题目描述
无

输入格式

第一行N、M和T，N为行，M为列，T为障碍总数。第二行起点坐标SX,SY，终点坐标FX,FY。接下来T行，每行为障碍点的坐标。

输出格式

给定起点坐标和终点坐标，问每个方格最多经过1次，从起点坐标到终点坐标的方案总数。

这道题一看就是

灰常简单的搜索

还需要些函数

先撸一下思路
好像没有什么可撸的

直接上代码

函数部分

void dfs(int x,int y) { if(x==fx&&y==fy)//判断是否走到终点  {         ans++;//累加  return; } else { for(int i=0;i<=3;i++)//四种方向  { int nx=x+dx[i];//x坐标  int ny=y+dy[i];//y坐标  if(tmp[nx][ny]==0&&a[nx][ny]==1)//是否走过 & 是否为陷阱  {                 tmp[x][y]=1; dfs(x+dx[i],y+dy[i]);                 tmp[x][y]=0; } } } } 

你可能会问：

if(tmp[nx][ny]==0&&a[nx][ny]==1)//是否走过 & 是否为陷阱  {             tmp[x][y]=1; dfs(x+dx[i],y+dy[i]);             tmp[x][y]=0; } 

会不会出界

当然是会的
但是你在看if里边
你就会明白

就算出界了

也不会出事

这就是这个代码的

精髓

上代码

#include<iostream> using namespace std; int a[10][10]; bool tmp[10][10]; int dx[4]={0,0,1,-1};//x坐标  int dy[4]={-1,1,0,0};//y坐标  int ans,fx,fy,sx,sy,T,n,m,l,r; void dfs(int x,int y) { if(x==fx&&y==fy)//判断是否走到终点  {         ans++;//累加  return; } else { for(int i=0;i<=3;i++)//四种方向  { int nx=x+dx[i];//x坐标  int ny=y+dy[i];//y坐标  if(tmp[nx][ny]==0&&a[nx][ny]==1)//是否走过 & 是否为陷阱  {                 tmp[x][y]=1; dfs(x+dx[i],y+dy[i]);                 tmp[x][y]=0; } } } } int main() {     cin>>n>>m>>T>>sx>>sy>>fx>>fy; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)    a[i][j]=1; for(int u=1;u<=T;u++) {         cin>>l>>r;         a[l][r]=0;//打个标记  } dfs(sx,sy);     cout<<ans; return 0; } 

复制的记得

爱赞不赞

爱吐槽就吐吧

有问题可以在下边提出来记得

@Y_bluefat