Lok Valley P1141 portal



I started to write this problem yesterday afternoon. Yesterday I always thought it was to find the farthest path, but after I handed it in, it was either WA or T. This morning my upperclassman told me that it was to find the largest connected block…

In fact, in addition to the problem of the examination, there is another problem, that is, the number of inquiries of this question may be as high as 100,000 times, even with BFS with low time complexity, it will surely T, why am I so sure? Because:

Upperclassmen are written with two DFS, the first of which marks all connected blocks,The second DFS is used to record each cell in the currently connected block.What does that mean? Let’s take a look at an example:

2 2
01
10
1 1
2 2
Copy the code

There are two questions in the sample, the first one is 1,1 and the second one is 2,2. But we can see that after the first query we can see that the whole graph is connected, i.eThese four positions all belong to the same connected blockSo after our first interview, we can totallyWrite down the answers for all four positionsIn this way, the next time you ask any cell of the connected block, you don’t need to search any more, just output the answer directly

The code is as follows:

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
#include <map>
#include <math.h>
#include <set>
#include <vector>
#include <stack>
#include <sstream>
#define ll long long
using namespace std;
int mov[4] [2] = {1.0.- 1.0.0.1.0.- 1};
int vis[1005] [1005];
int answ[1005] [1005];// Record the corresponding position of the answer
char mp[1005] [1005];
int n, m;
int ans;
int ct;
struct node
{
    char now;
    int x, y;
} fst, sec;
queue<node> q;
void bfs(a)
{
    while(! q.empty())
    {

        ans++;
        fst = q.front(a); q.pop(a);for (int i = 0; i < 4; i++)
        {
            int xx = fst.x + mov[i][0];
            int yy = fst.y + mov[i][1];
            if (xx < 1 || xx > n || yy < 1 || yy > n || mp[fst.x][fst.y] == mp[xx][yy] || vis[xx][yy] == ct)
                continue;
            vis[xx][yy] = ct;
            sec.now = mp[xx][yy];
            sec.x = xx;
            sec.y = yy;
            q.push(sec); }}}void dfs(int x, int y)
{
    answ[x][y] = ans;
    for (int i = 0; i < 4; i++)
    {
        int xx = x + mov[i][0];
        int yy = y + mov[i][1];
        if (xx < 1 || xx > n || yy < 1|| yy > n || vis[xx][yy] ! = ct)continue;
        vis[xx][yy] = 0;
        dfs(xx, yy); }}int main(a)
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> mp[i] + 1;
    while (m--)
    {
        ct++;
        ans = 0;
        int a, b;
        cin >> a >> b;
        if(answ[a][b] ! =0)
            cout << answ[a][b] << endl;
        else
        {
            while(! q.empty())
                q.pop(a); fst.now = mp[a][b]; fst.x = a; fst.y = b; q.push(fst);
            vis[a][b] = ct;
            bfs(a);dfs(a, b); cout << ans << endl; }}return 0;
}
Copy the code