題目描述

給定一個N*M（1≤N,M≤5）方格的迷宮，迷宮里有T處障礙，障礙處不可通過。給定起點坐標(biāo)和終點坐標(biāo)，問: 每個方格最多經(jīng)過1次，有多少種從起點坐標(biāo)到終點坐標(biāo)的方案。在迷宮中移動有上下左右四種方式，每次只能移動一個方格。數(shù)據(jù)保證起點上沒有障礙。

輸入輸出格式

輸入格式：

第一行N、M和T，N為行，M為列，T為障礙總數(shù)。第二行起點坐標(biāo)SX,SY，終點坐標(biāo)FX,FY。接下來T行，每行為障礙點的坐標(biāo)。

輸出格式：

給定起點坐標(biāo)和終點坐標(biāo)，問每個方格最多經(jīng)過1次，從起點坐標(biāo)到終點坐標(biāo)的方案總數(shù)。

輸入輸出樣例

輸入樣例#1：

2 2 1
1 1 2 2
1 2

輸出樣例#1：

1

源代碼

#include<iostream> using namespace std;int start_x,start_y,end_x,end_y; int map[101][101]={0}; int sum=0; void dfs(int a,int b);int main() {int n,m,t;int i,j;int x,y;cin>>n>>m>>t;//輸入行、列、障礙數(shù)cin>>start_x>>start_y>>end_x>>end_y;//輸入起點坐標(biāo)、終點坐標(biāo)for(i=1;i<=n;i++)//地圖初始化，為1時表示可以通過for(j=1;j<=m;j++)map[i][j]=1;for(i=1;i<=t;i++){cin>>x>>y;//輸入障礙物坐標(biāo)map[x][y]=0;//將障礙物坐標(biāo)記錄在地圖上}dfs(start_x,start_y);//從起點處開始搜索cout<<sum<<endl;//輸出方案數(shù)return 0; }void dfs(int x,int y) {if(x==end_x&&y==end_y)//搜索終止條件{sum++;return;}else//進(jìn)行回溯{map[x][y]=0;//保存當(dāng)前坐標(biāo)if(map[x][y-1]!=0)//左方{dfs(x,y-1);//左方搜索map[x][y-1]=1;//還原坐標(biāo)}if(map[x][y+1]!=0)//右方{dfs(x,y+1);//右方搜索map[x][y+1]=1;//還原坐標(biāo)}if(map[x-1][y]!=0)//上方{dfs(x-1,y);//上方搜索map[x-1][y]=1;//還原坐標(biāo)}if(map[x+1][y]!=0)//下方{dfs(x+1,y);//下方搜索map[x+1][y]=1;//還原坐標(biāo)}} }

?

總結(jié)

以上是生活随笔為你收集整理的迷宫（洛谷-P1605）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。