70求调(#1,#3,#10,#11TLE)

P1141 01迷宫

cgxd @ 2024-04-30 22:06:27

#include<bits/stdc++.h>
#define y1 yone
#define left leftn
using namespace std;
int n, m, x, y, cnt, left;
bool vis[1005][1005];
vector<bitset<1005>> v(1, 0);
deque<complex<int>> dq;
const complex<int> dir[] = {complex<int>(1, 0), complex<int>(0, 1), complex<int>(-1, 0), complex<int>(0, -1)};
int main(){
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        string s;
        cin >> s;
        reverse(s.begin(), s.end());
        s.push_back('0');
        bitset<1005> bs(s);
        v.push_back(bs);
    }v.push_back(0);
    while(m--){
        memset(vis, 0, sizeof(vis));
        cnt = 1;
        left = n * n - 1;
        cin >> x >> y;
        complex<int> c(x, y);
        vis[x][y] = 1;
        dq.assign(1, c);
        while(dq.size() and left){
            complex<int> c1(dq[0]);
            int x = c1.real(), y = c1.imag();
            dq.pop_front();
            for(complex<int> comp: dir){
                complex<int> c2(c1 + comp);
                int x1 = c2.real(), y1 = c2.imag();
                int k = vis[x1][y1] + 1;
                if(x1 <= 0 or x1 >= n + 1 or y1 <= 0 or y1 >= n + 1)
                    continue;
                if(vis[x1][y1] or !(v[x][y] xor v[x1][y1]))
                    continue;
                vis[x1][y1] = 1;
                cnt++;
                dq.push_back(c2);
                if(!(--left))
                    break;
            }
        }cout << cnt << '\n';
    }return 0;
}

by Lyx8058 @ 2024-05-01 13:26:52

要不看看快读?


by Lyx8058 @ 2024-05-01 13:28:02

但是你不用bfs好像做不了


|