鱼C论坛

 找回密码
 立即注册
查看: 1256|回复: 3

[已解决]C语言01迷宫

[复制链接]
发表于 2019-5-19 18:54:44 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
题目描述

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


最佳答案
2019-5-20 00:22:06
  1. //思路,首先将奇数格的1变0,0变1,然后计算每一块的大小,大小即为所需结果
  2. //使用并查集,减少赋值所需的工作量
  3. #include <stdio.h>


  4. typedef struct Block_Node_t{
  5.         struct Block_Node_t* root;
  6.         int count;
  7.         int val;
  8. }block_node;

  9. //获取根节点,并将集合扁平化,提高此后的速度;
  10. const int ROOTPTR_ARRSIZE=10;
  11. block_node* GetNodeRoot(block_node* node){
  12.         block_node** root_ptr[ROOTPTR_ARRSIZE];
  13.         int c_rootptr=0;
  14.         while (node->root!=NULL){
  15.                 if (c_rootptr>=ROOTPTR_ARRSIZE){
  16.                         printf("ROOTPTR_ARRSIZE太小!\n");
  17.                 }
  18.                 else{
  19.                         root_ptr[c_rootptr++]=&node->root;
  20.                 }
  21.                 node=node->root;
  22.         }
  23.        
  24.         int i;
  25.         for (i=0;i<c_rootptr-1;++i){
  26.                 *root_ptr[i]=node;
  27.         }
  28.         return node;
  29. }

  30. //根据节点获取所在块的节点数
  31. int CountNodeInBlock(block_node* node){
  32.         return GetNodeRoot(node)->count;
  33. }

  34. //初始化节点
  35. int InitNode(block_node* node){
  36.         node->root=NULL;
  37.         node->count=1;
  38. }

  39. //连接节点
  40. int linkNode(block_node* node1,block_node* node2){
  41.         if (GetNodeRoot(node1)==GetNodeRoot(node2)) return; //如果两节点已连接,直接返回
  42.         int n1=CountNodeInBlock(node1);
  43.         int n2=CountNodeInBlock(node2);
  44.         GetNodeRoot(node2)->root=GetNodeRoot(node1);
  45.         GetNodeRoot(node1)->count=n1+n2;
  46. }

  47. int main(){
  48.         int m,n,x,y,i;
  49.         //////////////////////////////////////////////////////
  50.         //获取数据
  51.         ////////////////////////////////////////////////
  52.         scanf("%d %d",&n,&m);
  53.         block_node map[n][n];
  54.         for (y=0;y<n;++y){
  55.                 for (x=0;x<n;++x){
  56.                         InitNode(&map[y][x]);
  57.                         scanf("%d",&map[y][x].val);
  58.                         if ((x+y&1)==1){   
  59.                                 map[y][x].val^=1; //使奇数格的值1变0,0变1;
  60.                         }
  61.                 }
  62.         }
  63.        
  64.         int query[m][2]; //记录询问,主要是为了让结构清晰
  65.         for (i=0;i<m;++i){
  66.                 scanf("%d %d",&query[i][0],&query[i][1]);
  67.         }
  68.        
  69.     //////////////////////////////////////////////////////
  70.         //遍历,并连接处于同一块的节点
  71.         ////////////////////////////////////////////////
  72.         for (y=0;y<n;++y){
  73.                 for (x=0;x<n;++x){
  74.                         if (x+1<n){  //只需要考虑下方和右方的节点,因为左方和上方的节点已经提前遍历了
  75.                                 if (map[y][x].val==map[y][x+1].val){
  76.                                         linkNode(&map[y][x],&map[y][x+1]);
  77.                                 }
  78.                         }
  79.                         if (y+1<n){
  80.                                 if (map[y][x].val==map[y+1][x].val){
  81.                                         linkNode(&map[y][x],&map[y+1][x]);
  82.                                 }
  83.                         }
  84.                 }
  85.         }
  86.        
  87.         for (i=0;i<m;++i){
  88.                 y=query[i][0]-1;
  89.                 x=query[i][1]-1;
  90.                 block_node *node=&map[y][x];
  91.                 printf("%d\n",CountNodeInBlock(node));
  92.         }
  93. }
复制代码
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2019-5-19 22:23:36 | 显示全部楼层
这是我自己写的代码,过了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);
        }
}
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2019-5-19 22:46:58 | 显示全部楼层
这道题给的数据如果做一个映射,偶数格的不变,奇数格的1变0,0变1(就像国际象棋棋盘一样),那么容易看出,0能到达的格子都是相邻且值为0的,而1能到达的格子都是相邻且值为1的。
也就是说,棋盘被划分成了一块一块的。

那么只需要一次遍历,求出每一块的大小,这一块的所有格子的(能移动到的格子的数目)就是块的大小。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2019-5-20 00:22:06 | 显示全部楼层    本楼为最佳答案   
  1. //思路,首先将奇数格的1变0,0变1,然后计算每一块的大小,大小即为所需结果
  2. //使用并查集,减少赋值所需的工作量
  3. #include <stdio.h>


  4. typedef struct Block_Node_t{
  5.         struct Block_Node_t* root;
  6.         int count;
  7.         int val;
  8. }block_node;

  9. //获取根节点,并将集合扁平化,提高此后的速度;
  10. const int ROOTPTR_ARRSIZE=10;
  11. block_node* GetNodeRoot(block_node* node){
  12.         block_node** root_ptr[ROOTPTR_ARRSIZE];
  13.         int c_rootptr=0;
  14.         while (node->root!=NULL){
  15.                 if (c_rootptr>=ROOTPTR_ARRSIZE){
  16.                         printf("ROOTPTR_ARRSIZE太小!\n");
  17.                 }
  18.                 else{
  19.                         root_ptr[c_rootptr++]=&node->root;
  20.                 }
  21.                 node=node->root;
  22.         }
  23.        
  24.         int i;
  25.         for (i=0;i<c_rootptr-1;++i){
  26.                 *root_ptr[i]=node;
  27.         }
  28.         return node;
  29. }

  30. //根据节点获取所在块的节点数
  31. int CountNodeInBlock(block_node* node){
  32.         return GetNodeRoot(node)->count;
  33. }

  34. //初始化节点
  35. int InitNode(block_node* node){
  36.         node->root=NULL;
  37.         node->count=1;
  38. }

  39. //连接节点
  40. int linkNode(block_node* node1,block_node* node2){
  41.         if (GetNodeRoot(node1)==GetNodeRoot(node2)) return; //如果两节点已连接,直接返回
  42.         int n1=CountNodeInBlock(node1);
  43.         int n2=CountNodeInBlock(node2);
  44.         GetNodeRoot(node2)->root=GetNodeRoot(node1);
  45.         GetNodeRoot(node1)->count=n1+n2;
  46. }

  47. int main(){
  48.         int m,n,x,y,i;
  49.         //////////////////////////////////////////////////////
  50.         //获取数据
  51.         ////////////////////////////////////////////////
  52.         scanf("%d %d",&n,&m);
  53.         block_node map[n][n];
  54.         for (y=0;y<n;++y){
  55.                 for (x=0;x<n;++x){
  56.                         InitNode(&map[y][x]);
  57.                         scanf("%d",&map[y][x].val);
  58.                         if ((x+y&1)==1){   
  59.                                 map[y][x].val^=1; //使奇数格的值1变0,0变1;
  60.                         }
  61.                 }
  62.         }
  63.        
  64.         int query[m][2]; //记录询问,主要是为了让结构清晰
  65.         for (i=0;i<m;++i){
  66.                 scanf("%d %d",&query[i][0],&query[i][1]);
  67.         }
  68.        
  69.     //////////////////////////////////////////////////////
  70.         //遍历,并连接处于同一块的节点
  71.         ////////////////////////////////////////////////
  72.         for (y=0;y<n;++y){
  73.                 for (x=0;x<n;++x){
  74.                         if (x+1<n){  //只需要考虑下方和右方的节点,因为左方和上方的节点已经提前遍历了
  75.                                 if (map[y][x].val==map[y][x+1].val){
  76.                                         linkNode(&map[y][x],&map[y][x+1]);
  77.                                 }
  78.                         }
  79.                         if (y+1<n){
  80.                                 if (map[y][x].val==map[y+1][x].val){
  81.                                         linkNode(&map[y][x],&map[y+1][x]);
  82.                                 }
  83.                         }
  84.                 }
  85.         }
  86.        
  87.         for (i=0;i<m;++i){
  88.                 y=query[i][0]-1;
  89.                 x=query[i][1]-1;
  90.                 block_node *node=&map[y][x];
  91.                 printf("%d\n",CountNodeInBlock(node));
  92.         }
  93. }
复制代码
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-7-2 05:04

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表