P1141 01迷宫
题目描述
有一个仅由数字0与1组成的n×n格迷宫。若你位于一格0上，那么你可以移动到相邻4格中的某一格1上，同样若你位于一格1上，那么你可以移动到相邻4格中的某一格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
说明
所有格子互相可达。
对于20%的数据，n≤10；
对于40%的数据，n≤50；
对于50%的数据，m≤5；
对于60%的数据，n≤100，m≤100；
对于100%的数据，n≤1000，m≤100000。
一直wa 7个点找了半天也不知道哪错了，结果发现是读入的时候出了问题ORZ
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 5000
using namespace std;
char a[N][N];
bool vis[N][N],g[N][N];
int n,m,x,y,ans,f[N][N];
]={,,,-},yy[]={,-,,};
int read()
{
,f=; char ch=getchar();
; ch=getchar();}
+ch-'; ch=getchar();}
return x*f;
}
void dfs(int x,int y)
{
||y<||x>n||y>n||vis[x][y]||g[x][y]) return ;
if(!g[x][y]) ans++;
vis[x][y]=true,g[x][y]=true;
;i<;i++)
{
int fx=x+xx[i],fy=y+yy[i];
if(a[fx][fy]!=a[x][y])
dfs(fx,fy);
}
vis[x][y]=false;
}
int main()
{
n=read(),m=read();
;i<=n;i++)
{
;j<=n;j++)
cin>>a[i][j];
}
while(m--)
{
x=read(),y=read();
ans=;
memset(g,,sizeof(g));
memset(vis,,sizeof(vis));
dfs(x,y);
printf("%d\n",ans);
}
;
}
爆搜70
正解：记忆化搜索
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 5000
using namespace std;
char a[N][N];
bool vis[N][N],g[N][N];
,d[],f[N][N];
]={,,,-},yy[]={,-,,};
int read()
{
,f=; char ch=getchar();
; ch=getchar();}
+ch-'; ch=getchar();}
return x*f;
}
void dfs(int x,int y)
{
||y<||x>n||y>n||f[x][y]) return ;
f[x][y]=cnt;ans++;
;i<;i++)
{
int fx=x+xx[i],fy=y+yy[i];
if(a[fx][fy]!=a[x][y])
dfs(fx,fy);
}
d[cnt]=ans;
}
int main()
{
n=read(),m=read();
;i<=n;i++)
{
;j<=n;j++)
cin>>a[i][j];
}
while(m--)
{
x=read(),y=read();
if(!f[x][y])
{
ans=;
dfs(x,y);cnt++;
}
ans=d[f[x][y]];
printf("%d\n",ans);
}
;
}
记忆化搜索