NC216127. 小C与迷宫
描述
输入描述
第1行为两个正整数n≤1000和m≤100000代表了迷宫大小是n*n大与询问次数m次。下面n行，每行n个字符，字符只可能是0或者0,字符之间没有空格。
接下来m行，每行2个用空格分隔的正整数 1<=i<=n , 1<=j<=n 对应了迷宫中第i行第j列的一个格子，询问从这一格开始,能移动到多少格。
输出描述
m行，对于每个询问输出相应答案。
示例1
输入:
4 4 1010 0111 1101 0010 1 1 2 2 3 3 4 4
输出:
9 9 7 7
C++(clang++11) 解法, 执行用时: 303ms, 内存消耗: 10028K, 提交时间: 2021-04-04 19:54:17
#include<iostream>
#include<string>
#include<string.h>
using namespace std;
int n;
string a[100000];
int b[1005][1005];
int num[100010];
void dfs(int x,int y,char z,int dp)
{
if(x<0||x>=n||y<0||y>=n||b[x][y]!=-1||a[x][y]==z)
return ;
b[x][y]=dp;
num[dp]++;
dfs(x-1,y,a[x][y],dp);
dfs(x+1,y,a[x][y],dp);
dfs(x,y-1,a[x][y],dp);
dfs(x,y+1,a[x][y],dp);
}
int main()
{
int m;
cin>>n>>m;
for(int i=0;i<n;i++)
cin>>a[i];
memset(b,-1,sizeof(b));
for(int i=0;i<m;i++)
{
int x,y;
cin>>x>>y;
if(b[x-1][y-1]==-1)
dfs(x-1,y-1,'2',i);
else
num[i]=num[b[x-1][y-1]];
cout<<num[i]<<endl;
}
return 0;
}