题目描述
有一个仅由数字 0 与 1 组成的 n×m 格迷宫。若你位于一格 0 上,那么你可以移动到相邻 4 格中的某一格 1 上,同样若你位于一格 1 上,那么你可以移动到相邻 4 格中的某一格 0 上。
你的任务是:对于给定的迷宫,询问 k 次从某一格开始能移动到多少个格子(包含自身)。
输入
第 1 行为两个正整数 n,m,k。
下面 n 行,每行 m 个字符,字符只可能是 0 或者 1,字符之间没有空格。
移动迷宫第一季免费观看、 接下来 k 行每行给出一个点的在坐标。
输出
对于每个坐标输出一行一个整数表示该点能移动到的格子数(包括自身)。
样例输入
2 3 4
011
100
1 1
2 2
1 3
2 3
样例输出
4
4
2
2
数据规模与约定
时间限制:1 s
内存限制:256 M
100% 的数据保证 1≤n,m≤3000,1≤k≤30000
#include <iostream>
#include <queue>
using namespace std;char map[3005][3005];
int check[3005][3005];
int m, n,k, sx, sy;
int ans = 0, mmax;
int dir[4][2] = { 0,1,1,0,0,-1,-1,0 };
struct node {int x, y;
};
queue<node> que;
void func(int x, int y) {for (int i = 0; i < 4; i++) {int tx = x + dir[i][0];int ty = y + dir[i][1];if (tx<1 || ty<1 || tx>n || ty>m) {continue;}if (map[tx][ty] != map[x][y]&&check[tx][ty]==0) {ans++;check[tx][ty] = 1;que.push({ tx, ty });func(tx, ty);}}
}
int main() {cin >> n >> m>>k;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cin >> map[i][j];}}for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (check[i][j] == 0) {ans = 1;check[i][j] = 1;que.push({ i, j });func(i, j);while (!que.empty()) {node temp = que.front();que.pop();check[temp.x][temp.y] = ans;}}}}for (int i = 0; i < k; i++) {cin >> sx >> sy;cout << check[sx][sy] << endl;}return 0;
}
版权声明:本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。
工作时间:8:00-18:00
客服电话
电子邮件
admin@qq.com
扫码二维码
获取最新动态