C语言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行，对于每个询问输出相应答案。
输入样例：
2 2
01
10
1 1
2 2
输出样例：
4
4
说明
对于60%的数据，n≤100,m≤100；
对于100%的数据，n≤1000,m≤100000。
这是我自己写的代码，过了7组数据，3组超时，请问如何改进提高效率呢？
#include<stdio.h>
#include<string.h>
int k;
char s,a;
void fun(int a,int b)
{
if(s=='0')
{
s=0;
if(s=='1')
{
k++;
fun(a-1,b);
}
if(s=='1')
{
k++;
fun(a+1,b);
}
if(s=='1')
{
k++;
fun(a,b+1);
}
if(s=='1')
{
k++;
fun(a,b-1);
}
}
else if(s=='1')
{
s=0;
if(s=='0')
{
k++;
fun(a-1,b);
}
if(s=='0')
{
k++;
fun(a+1,b);
}
if(s=='0')
{
k++;
fun(a,b+1);
}
if(s=='0')
{
k++;
fun(a,b-1);
}
}
}
int main()
{
memset(s,0,sizeof(s));
int i,n,m,x1,y1;
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)scanf("%s",s);
memcpy(a,s,sizeof(s));
while(m--)
{
memcpy(s,a,sizeof(a));
scanf("%d%d",&x1,&y1);
k=1;
fun(x1-1,y1-1);
printf("%d\n",k);
}
} 这道题给的数据如果做一个映射，偶数格的不变，奇数格的1变0,0变1（就像国际象棋棋盘一样），那么容易看出，0能到达的格子都是相邻且值为0的，而1能到达的格子都是相邻且值为1的。
也就是说，棋盘被划分成了一块一块的。
那么只需要一次遍历，求出每一块的大小，这一块的所有格子的（能移动到的格子的数目）就是块的大小。
//思路，首先将奇数格的1变0,0变1，然后计算每一块的大小，大小即为所需结果
//使用并查集，减少赋值所需的工作量
#include <stdio.h>
typedef struct Block_Node_t{
struct Block_Node_t* root;
int count;
int val;
}block_node;
//获取根节点，并将集合扁平化，提高此后的速度；
const int ROOTPTR_ARRSIZE=10;
block_node* GetNodeRoot(block_node* node){
block_node** root_ptr;
int c_rootptr=0;
while (node->root!=NULL){
if (c_rootptr>=ROOTPTR_ARRSIZE){
printf("ROOTPTR_ARRSIZE太小!\n");
}
else{
root_ptr=&node->root;
}
node=node->root;
}
int i;
for (i=0;i<c_rootptr-1;++i){
*root_ptr=node;
}
return node;
}
//根据节点获取所在块的节点数
int CountNodeInBlock(block_node* node){
return GetNodeRoot(node)->count;
}
//初始化节点
int InitNode(block_node* node){
node->root=NULL;
node->count=1;
}
//连接节点
int linkNode(block_node* node1,block_node* node2){
if (GetNodeRoot(node1)==GetNodeRoot(node2)) return; //如果两节点已连接，直接返回
int n1=CountNodeInBlock(node1);
int n2=CountNodeInBlock(node2);
GetNodeRoot(node2)->root=GetNodeRoot(node1);
GetNodeRoot(node1)->count=n1+n2;
}
int main(){
int m,n,x,y,i;
//////////////////////////////////////////////////////
//获取数据
////////////////////////////////////////////////
scanf("%d %d",&n,&m);
block_node map;
for (y=0;y<n;++y){
for (x=0;x<n;++x){
InitNode(&map);
scanf("%d",&map.val);
if ((x+y&1)==1){
map.val^=1; //使奇数格的值1变0,0变1；
}
}
}
int query; //记录询问，主要是为了让结构清晰
for (i=0;i<m;++i){
scanf("%d %d",&query,&query);
}
//////////////////////////////////////////////////////
//遍历，并连接处于同一块的节点
////////////////////////////////////////////////
for (y=0;y<n;++y){
for (x=0;x<n;++x){
if (x+1<n){//只需要考虑下方和右方的节点，因为左方和上方的节点已经提前遍历了
if (map.val==map.val){
linkNode(&map,&map);
}
}
if (y+1<n){
if (map.val==map.val){
linkNode(&map,&map);
}
}
}
}
for (i=0;i<m;++i){
y=query-1;
x=query-1;
block_node *node=↦
printf("%d\n",CountNodeInBlock(node));
}
}
页:
[1]