[已解决]C语言01迷宫

客天恺_hqkcq

题目描述

有一个仅由数字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。

最佳答案

月排行榜 / 总排行榜

Croper

2019-5-20 00:22:06

//思路，首先将奇数格的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[ROOTPTR_ARRSIZE];
        int c_rootptr=0;
        while (node->root!=NULL){
                if (c_rootptr>=ROOTPTR_ARRSIZE){
                        printf("ROOTPTR_ARRSIZE太小!\n");
                }
                else{
                        root_ptr[c_rootptr++]=&node->root;
                }
                node=node->root;
        }
        
        int i;
        for (i=0;i<c_rootptr-1;++i){
                *root_ptr[i]=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[n][n];
        for (y=0;y<n;++y){
                for (x=0;x<n;++x){
                        InitNode(&map[y][x]);
                        scanf("%d",&map[y][x].val);
                        if ((x+y&1)==1){   
                                map[y][x].val^=1; //使奇数格的值1变0,0变1； 
                        }
                }
        }
        
        int query[m][2]; //记录询问，主要是为了让结构清晰 
        for (i=0;i<m;++i){
                scanf("%d %d",&query[i][0],&query[i][1]);
        }
        
    //////////////////////////////////////////////////////
        //遍历，并连接处于同一块的节点 
        //////////////////////////////////////////////// 
        for (y=0;y<n;++y){
                for (x=0;x<n;++x){
                        if (x+1<n){  //只需要考虑下方和右方的节点，因为左方和上方的节点已经提前遍历了 
                                if (map[y][x].val==map[y][x+1].val){
                                        linkNode(&map[y][x],&map[y][x+1]);
                                }
                        }
                        if (y+1<n){
                                if (map[y][x].val==map[y+1][x].val){
                                        linkNode(&map[y][x],&map[y+1][x]);
                                }
                        }
                }
        }
        
        for (i=0;i<m;++i){
                y=query[i][0]-1;
                x=query[i][1]-1;
                block_node *node=&map[y][x];
                printf("%d\n",CountNodeInBlock(node));
        }
}

跳转到最佳答案楼层

客天恺_hqkcq

这是我自己写的代码，过了7组数据，3组超时，请问如何改进提高效率呢？
#include<stdio.h>
#include<string.h>
int k;
char s[1010][1010],a[1010][1010];
void fun(int a,int b)
{
        if(s[a][b]=='0')
        {
                s[a][b]=0;
                if(s[a-1][b]=='1')
                {
                        k++;
                        fun(a-1,b);
                }
                if(s[a+1][b]=='1')
                {
                        k++;
                        fun(a+1,b);
                }
                if(s[a][b+1]=='1')
                {
                        k++;
                        fun(a,b+1);
                }
                if(s[a][b-1]=='1')
                {
                        k++;
                        fun(a,b-1);
                }
        }
        else if(s[a][b]=='1')
        {
                s[a][b]=0;
                if(s[a-1][b]=='0')
                {
                        k++;
                        fun(a-1,b);
                }
                if(s[a+1][b]=='0')
                {
                        k++;
                        fun(a+1,b);
                }
                if(s[a][b+1]=='0')
                {
                        k++;
                        fun(a,b+1);
                }
                if(s[a][b-1]=='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[i]);
        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);
        }
}

Croper

这道题给的数据如果做一个映射，偶数格的不变，奇数格的1变0,0变1（就像国际象棋棋盘一样），那么容易看出，0能到达的格子都是相邻且值为0的，而1能到达的格子都是相邻且值为1的。
也就是说，棋盘被划分成了一块一块的。

那么只需要一次遍历，求出每一块的大小，这一块的所有格子的（能移动到的格子的数目）就是块的大小。

Croper

//思路，首先将奇数格的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[ROOTPTR_ARRSIZE];
        int c_rootptr=0;
        while (node->root!=NULL){
                if (c_rootptr>=ROOTPTR_ARRSIZE){
                        printf("ROOTPTR_ARRSIZE太小!\n");
                }
                else{
                        root_ptr[c_rootptr++]=&node->root;
                }
                node=node->root;
        }
        
        int i;
        for (i=0;i<c_rootptr-1;++i){
                *root_ptr[i]=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[n][n];
        for (y=0;y<n;++y){
                for (x=0;x<n;++x){
                        InitNode(&map[y][x]);
                        scanf("%d",&map[y][x].val);
                        if ((x+y&1)==1){   
                                map[y][x].val^=1; //使奇数格的值1变0,0变1； 
                        }
                }
        }
        
        int query[m][2]; //记录询问，主要是为了让结构清晰 
        for (i=0;i<m;++i){
                scanf("%d %d",&query[i][0],&query[i][1]);
        }
        
    //////////////////////////////////////////////////////
        //遍历，并连接处于同一块的节点 
        //////////////////////////////////////////////// 
        for (y=0;y<n;++y){
                for (x=0;x<n;++x){
                        if (x+1<n){  //只需要考虑下方和右方的节点，因为左方和上方的节点已经提前遍历了 
                                if (map[y][x].val==map[y][x+1].val){
                                        linkNode(&map[y][x],&map[y][x+1]);
                                }
                        }
                        if (y+1<n){
                                if (map[y][x].val==map[y+1][x].val){
                                        linkNode(&map[y][x],&map[y+1][x]);
                                }
                        }
                }
        }
        
        for (i=0;i<m;++i){
                y=query[i][0]-1;
                x=query[i][1]-1;
                block_node *node=&map[y][x];
                printf("%d\n",CountNodeInBlock(node));
        }
}