50分,求助~
  • 板块P1605 迷宫
  • 楼主ssjl
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/7/8 12:24
  • 上次更新2023/10/27 21:30:30
查看原帖
50分,求助~
745640
ssjl楼主2022/7/8 12:24
#include <iostream>
#include <algorithm>
#include <cstring>
#include <map> 
#include <string>
#include <queue>

using namespace std;

const int N = 6;

typedef long long ll;

int n, m, k;
int cnt;
int g[N][N];
int st[N][N];
int sx, sy, fx, fy;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

void bfs()
{
    queue<pair<int, int>> q;
    q.push({sx, sy});
    st[sx][sy] = 1;
    
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        int x = t.first, y = t.second;
        
        for(int i = 0; i < 4; i ++)
        {
            int a = x + dx[i];
            int b = y + dy[i];
            //走过 有障碍 越界
            if( st[a][b] 
                || g[a][b] 
                || a == 0 || b == 0 
                || a > n || b > m)
                continue;
            
            //走到了终点
            if(a == fx && b == fy)
            {
                cnt ++;
                continue;
            }

            //入队
            q.push({a, b});
            st[a][b] = true;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m >> k;
    
    cin >> sx >> sy >> fx >> fy;
    
    for(int i = 0; i < k; i ++)
    {
        int a, b;
        cin >> a >> b;
        g[a][b] = 1;
    }
    
    bfs();
    
    if(g[fx][fy]) cout << 0 << endl;
    else cout << cnt << endl;
	
	return 0;
}
2022/7/8 12:24
加载中...