正规网站建设制作,企业系统管理软件,网站建设人员分工表,会展设计专业学什么01迷宫
题目描述
有一个仅由数字 0 0 0 与 1 1 1 组成的 n n n \times n nn 格迷宫。若你位于一格 0 0 0 上#xff0c;那么你可以移动到相邻 4 4 4 格中的某一格 1 1 1 上#xff0c;同样若你位于一格 1 1 1 上#xff0c;那么你可以移动到相邻 4 4 4 格中的某一…01迷宫
题目描述
有一个仅由数字 0 0 0 与 1 1 1 组成的 n × n n \times n n×n 格迷宫。若你位于一格 0 0 0 上那么你可以移动到相邻 4 4 4 格中的某一格 1 1 1 上同样若你位于一格 1 1 1 上那么你可以移动到相邻 4 4 4 格中的某一格 0 0 0 上。
你的任务是对于给定的迷宫询问从某一格开始能移动到多少个格子包含自身。
输入格式
第一行为两个正整数 n , m n,m n,m。
下面 n n n 行每行 n n n 个字符字符只可能是 0 0 0 或者 1 1 1字符之间没有空格。
接下来 m m m 行每行两个用空格分隔的正整数 i , j i,j i,j对应了迷宫中第 i i i 行第 j j j 列的一个格子询问从这一格开始能移动到多少格。
输出格式 m m m 行对于每个询问输出相应答案。
样例 #1
样例输入 #1
2 2
01
10
1 1
2 2样例输出 #1
4
4提示
对于样例所有格子互相可达。
对于 20 % 20\% 20% 的数据 n ≤ 10 n \leq 10 n≤10对于 40 % 40\% 40% 的数据 n ≤ 50 n \leq 50 n≤50对于 50 % 50\% 50% 的数据 m ≤ 5 m \leq 5 m≤5对于 60 % 60\% 60% 的数据 n , m ≤ 100 n,m \leq 100 n,m≤100对于 100 % 100\% 100% 的数据 1 ≤ n ≤ 1000 1\le n \leq 1000 1≤n≤1000 1 ≤ m ≤ 100000 1\le m \leq 100000 1≤m≤100000。
思路分析 这个题看一下就知道要用dfs或者bfs但是直接爆搜的话会肯定会超时最后只能过70分所以我们要想一个方法来优化首先这个题是需要记录每一个开始走可以走到的最大的步骤设想一下啊如果有一条这样的路径存在a–b–c–d那么无论a还是b还是c还是d他们可以走到的最远的路径都是这个4所以我们不必要每一个点都开始搜只要在满足的一条路上全都标记一下类似于并查集但是这里根本不用那么麻烦直接用一个数组来标记即可直接上代码代码有详解
#includeiostream
#includealgorithm
#includecstring
#includestring
#includequeue
#define x first
#define y second
const int N 1010;
using namespace std;
typedef pairint, intPII;
int n, m,a,b;
char g[N][N];
bool st[N][N];
int vis[N][N];//记录联通区间
int dx[] { 1,0,-1,0 };
int dy[] { 0,1,0,-1 };//方向
int res,k1;
int ans[20000005];//存档答案
queuePIIq;
void bfs(int a,int b)
{q.push({ a,b });while (q.size()){auto t q.front();q.pop();for (int i 0; i 4; i){int xx t.x dx[i];int yy t.y dy[i];if (xx 1 yy 1 xx n yy n g[t.x][t.y] ! g[xx][yy] !vis[xx][yy])//判断合法{vis[xx][yy] k;//起到标记作用q.push({ xx,yy });res;//答案数加一}}}
}
int main()
{cin n m;for (int i 1; i n; i)for (int j 1; j n; j)cin g[i][j];for (int i 1; i n; i)for (int j 1; j n; j) {if (!vis[i][j])//没搜过就开搜{res 1;//重置点数为1因为包含这个点本身vis[i][j] k;//标记bfs(i, j);ans[k] res;k;}}while (m--){cin a b;cout ans[vis[a][b]] endl;} return 0;
}
