p1141 01迷宫

发表于 更新于 分类于 ， 阅读次数： Waline： 本文字数： 2.6k 阅读时长 ≈ 2 分钟

题目链接

题目描述

有一个仅由数字0与1组成的n×n格迷宫。若你位于一格0上，那么你可以移动到相邻44格中的某一格1上，同样若你位于一格1上，那么你可以移动到相邻44格中的某一格0上。

你的任务是：对于给定的迷宫，询问从某一格开始能移动到多少个格子（包含自身）。

输入输出格式

输入格式：

第1行为两个正整数n,m。

下面n行，每行n个字符，字符只可能是0或者1，字符之间没有空格。

接下来m行，每行2个用空格分隔的正整数i,j，对应了迷宫中第i行第j列的一个格子，询问从这一格开始能移动到多少格。

输出格式：

m行，对于每个询问输出相应答案。

输入输出样例

输入样例#1:

2 2

01

10

1 1

2 2

输出样例#1:

4

4

解题思路

一开始我直接就dfs直接搜了，但是TLE了3个数据。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;
const int maxn=1010;
char a[maxn][maxn];
int dir[][2]={{-1,0},{1,0},{0,-1},{0,1}};
int vis[maxn][maxn];
int n,m;
int ans;
int max_ans;
void dfs(int x,int y,char temp)
{
    vis[x][y]=1;
    if(x<1||x>n||y<1||y>n) return;
    else {
        for(int i=0;i<4;i++){
            int dx=x+dir[i][0];
            int dy=y+dir[i][1];
            if(dx>0&&dx<=n&&dy>0&&dy<=n&&vis[dx][dy]==0&&a[dx][dy]!=temp){
                if(vis[dx][dy]==0) ans++;
                vis[dx][dy]++;
                temp=a[dx][dy];
                if(ans>max_ans) max_ans=ans;
                dfs(dx,dy,temp);
                temp=a[x][y];
            }
        }
    }
}

int main()
{
    int start,end;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>a[i][j];
    while(m--){
        cin>>start>>end;
        memset(vis,0,sizeof(vis));
        ans=1;max_ans=1;
        dfs(start,end,a[start][end]);
        cout<<max_ans<<endl;
    }
    return 0;
}

听大佬说可以用并查集可以直接写，但是不会（无奈）

想了许久，发现如果每次查询一个就重新查会TLE,那么是不是只要我们查过了的我们就标志下，下次就不用再查了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bit/stdc++.h>
using namespace std;
const int maxn=1000010;
int x,y,f[1010][1010];
int n,m,ans[maxn];
char s[1010][1010];

void dfs(int r,int c,int z,int l)
{
    if(r<0||r>=n||c<0||c>=n||f[r][c]!=-1||s[r][c]-'0'!=z) return;
    f[r][c]=l;ans[l]++;//记录个数
    dfs(r-1,c,!z,l);
    dfs(r+1,c,!z,l);
    dfs(r,c-1,!z,l);
    dfs(r,c+1,!z,l);
}

int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>s[i][j];
    memset(f,-1,sizeof(f));
    for(int i=0;i<m;i++){
        cin>>x>>y;
        x--;y--;
        if(f[x][y]==-1) dfs(x,y,s[x][y]-'0',i);
        else ans[i]=ans[f[x][y]];//已经找过了
    }
    for(int i=0;i<m;i++)
        cout<<ans[i]<<endl;
    return 0;
}