给定起点坐标和终点坐标, 问每个方格最多经过 1 次, 从起点坐标到终点坐标的方案总数.
开一个 vis 来记录点是否走过, 如果没走过, 就走点, 把 vis 更新为 1, 继续搜索, 后再更新回 0 以便下次利用.
dir1 和 dir2 的四种组合表示四种方向并判断走之后的点是否越界
- #include<iostream>
- #include<cstdlib>
- #include<cstdio>
- #include<cmath>
- using namespace std;
- int map[6][6];// 地图;
- bool vis[6][6];// 走过的标记;
- int dx[4]={0,0,1,-1};
- int dy[4]={-1,1,0,0};
- int total,fx,fy,sx,sy,T,n,m,l,r;
- void dfs(int x,int y)
- {
- if(x==fx&&y==fy)
- {
- total++;
- return;
- }
- else
- {
- for(int i=0;i<=3;i++)
- {
- if(vis[x+dx[i]][y+dy[i]]==0&&map[x+dx[i]][y+dy[i]]==1)
- {
- vis[x][y]=1;
- dfs(x+dx[i],y+dy[i]);
- vis[x][y]=0;
- }
- }
- }
- }
- int main()
- {
- cin>>n>>m>>T;
- for(int i=1;i<=n;i++)
- for(int j=1;j<=m;j++)
- map[i][j]=1;
- scanf ("%d%d",&sx,&sy);
- scanf ("%d%d",&fx,&fy);
- for(int u=1;u<=T;u++)
- {
- scanf("%d%d",&l,&r);
- map[l][r]=0;
- }
- dfs(sx,sy);
- cout<<total;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3264393.html