P1605 迷宫dfs做法
  • 板块P1605 迷宫
  • 楼主nezi086
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/4/19 16:27
  • 上次更新2024/4/19 19:30:50
查看原帖
P1605 迷宫dfs做法
1186903
nezi086楼主2024/4/19 16:27
#include<iostream>
using namespace std;
int n,m,t;//n为纵坐标,m为横坐标;
const int N = 10;
char M[N][N];//地图
int res = 0;//res为方格数
int ans = 0;//ans为方案数
int sx,sy,fx,fy;  
bool st[N][N];
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};//定义方向向量数组
void dfs(int x,int y)//当前移动坐标
{
    if(x == fx&& y == fy)
    {
        ans++;
        return;
    }
    for(int i = 0 ; i < 4 ; i++)
        {
        int a = x + dx[i], b = y + dy[i];
        if(M[a][b] == '#')continue;
        if(a < 1 ||b < 1 ||  a > m || b >n)continue;
        if(st[a][b])continue;
        st[a][b] = true;
        dfs(a,b);
        st[a][b] = false;
        }
    return;
}



int main()
{
    cin>>n>>m>>t;
    for(int i = 1 ; i <= m ; i++)
    {
        for(int j = 1 ; j <= n ; j++)
        {
            M[i][j] = '.';
        }
    }
    
    cin>>sx>>sy>>fx>>fy;
    M[sx][sy] = '@';//起点
    M[fx][fy] = '*';//终点
    
    while(t--)
    {
        int o = 0,p = 0;
        cin>>o>>p;//o,p更新为新的障碍坐标;
        M[o][p] = '#';
    }
    for(int i = 1 ; i <= m ; i ++)
    {
        for(int j = 1 ; j <= n ; j++)
        {
            if(M[i][j] == '@')
            {
                st[i][j] = true;
                dfs(i,j);
            }
        }
    }
    /*res ++;
    cout<<res<<endl;
    for(int i = 1 ; i <= m ; i++)
    {
        for(int j = 1 ; j <= n ; j++)
        {
            cout<<M[i][j]<<"  ";
        }
        cout<<endl;
    }*/
    cout<<ans;
    return 0;
}
2024/4/19 16:27
加载中...