本题算法有点复杂,涉及了十字链表.
我得解法如下.
setlink(){setsublink()}建立十字链表把处于统一房间的块串起来.
setsumlink()将房间两两组合,建立一个结构数组,设房间总数为headnum,该数组长度为headnum*(headnum-1)/2,改结构的元素为两房间快数之和以及指向两个房间头的
指针.
sortsumlink()将该结构数组排序,从大到小.
然后以次从该结构数组中seekdoor()寻找连接两个房间的关键之门,并返回一个
结构food,即为所求结果,opendoor(),打开关键之门.
input file:
7

4

11 6 11 6 3 10 6

7 9 6 13 5 15 5

1 10 12 7 13 7 5

13 11 10 8 10 12 13

output file:

2    2
3    2
16

16为所求两房间之和.
为方便理解我得算法,我在程序中将该房间画了下来.
以下是我的程序,有兴趣的同学可稍加研究.

#include "graphics.h"
#include "stdlib.h"
#include "conio.h"
#include "stdio.h"
#include "alloc.h"
#include "dos.h"

typedef struct p
{
int west;
int north;
int east;
int south;
int isowned;
struct q*point;
}road;

typedef struct r
{
int x;
int y;
struct r*next;
}seed;

typedef struct q
{
int sum;
struct q*next;
struct r*first;
}header;

typedef struct t
{
int comsum;
struct q*head1;
struct q*head2;
}combinate;

typedef struct s
{
int lx;
int ly;
int rx;
int ry;
}result;
int color;

void setlink(header*,road*,int,int,int*);
void setsublink(header*,seed*,road*,int,int,int,int);
void setsumlink(header*,combinate*);
void sortsumlink(combinate*,int);
result*seekdoor(road*,seed*,header*,int,int);
void opendoor(result*);

FILE*fout;

void main(void)
{
FILE*fin;
int driver=VGA,mode=VGAHI,headnum=0;
int*wall,n,m,i,j,k;
combinate*data;
road*path;
header*head,*rear;
result*food;
head=rear=(header*)malloc(sizeof(header));
rear->first=head->first=NULL;
rear->next=head->next=NULL;
rear->sum=head->sum=0;
initgraph(&driver,&mode,"f:\\tc20\\bgi");
setcolor(CYAN);
if(!(fin=fopen("f:\\ty.txt","r")))
{
  printf("cannot find ty.txt.");
  return;
}
if(!(fout=fopen("f:\\tx.txt","w")))
{
  printf("cannot open tx.txt.");
  return;
}
fscanf(fin,"%d %d",&n,&m);
wall=(int*)malloc(m*n*sizeof(int));
path=(road*)calloc(m*n,sizeof(road));
for(i=0;i<m;i++)
for(j=0;j<n;j++)
{
  fscanf(fin,"%d",&wall[n*i+j]);
  if(!wall[n*i+j])continue;
  if(wall[n*i+j]&1)
{
  line(100+20*j-10,100+20*i-10,100+20*j-10,100+20*i+10);
  path[n*i+j].west=1;
  }
if(wall[n*i+j]&2)
{
  line(100+20*j-10,100+20*i-10,100+20*j+10,100+20*i-10);
  path[n*i+j].north=1;
  }
if(wall[n*i+j]&4)
{
  line(100+20*j+10,100+20*i-10,100+20*j+10,100+20*i+10);
  path[n*i+j].east=1;
  }
if(wall[n*i+j]&8)
{
  line(100+20*j-10,100+20*i+10,100+20*j+10,100+20*i+10);
  path[n*i+j].south=1;
  }
}
setlink(rear,path,m,n,&headnum);
data=(combinate*)malloc(headnum*(headnum-1)/2*sizeof(combinate));
setsumlink(head,data);
sortsumlink(data,headnum*(headnum-1)/2);
for(i=0;i<headnum*(headnum-1)/2;i++)
{
food=seekdoor(path,data[i].head1->first,data[i].head2,m,n);
if(!food)continue;
fprintf(fout,"%d\t%d\n\n\n",food->lx,food->ly);
fprintf(fout,"%d\t%d\n\n\n",food->rx,food->ry);
fprintf(fout,"%d",data[i].comsum);
opendoor(food);
getch();
return;
}
getch();
}



待续

void setlink(header*rear,road*path,int m,int n,int*headnum)
{
int x,y,i,startx=0,t=0,starty=0,flag=0;
header*node;
seed*front;
while(1)
{
  for(t=x=startx;x<m;startx=++x)
  {
  if(t==startx)y=starty;
  else y=0;
  for(;y<n;starty=++y)
    if(!path[n*x+y].isowned){flag=1;break;}
  if(flag)break;
    }
if(x==m&&y==n)break;
flag=0;
color++;
(*headnum)++;
front=(seed*)malloc(sizeof(seed));
node=(header*)malloc(sizeof(header));
front->x=x;
front->y=y;
front->next=NULL;
node->sum=0;
node->next=NULL;
node->first=NULL;
rear->next=node;
rear=rear->next;
rear->first=front;
path[n*x+y].isowned=1;
path[n*x+y].point=rear;
for(i=0;i<10;i++)
delay(10000);
putpixel(100+20*y,100+20*x,color);
rear->sum++;
setsublink(rear,front,path,m,n,x,y);
  }
}


void setsublink(header*rear,seed*front,road*path,int m,int n,int x,int y)
{
seed*node;
int i;
if(!path[n*x+y].north)
if(!path[n*(x-1)+y].isowned)
{
  node=(seed*)malloc(sizeof(seed));
  node->x=x-1;
  node->y=y;
  node->next=NULL;
  front->next=node;
  front=front->next;
  path[n*(x-1)+y].isowned=1;
  path[n*(x-1)+y].point=rear;
  for(i=0;i<10;i++)
  delay(10000);
  putpixel(100+20*y,80+20*x,color);
  rear->sum++;
  setsublink(rear,front,path,m,n,x-1,y);
}
if(!path[n*x+y].south)
if(!path[n*(x+1)+y].isowned)
{
  node=(seed*)malloc(sizeof(seed));
  node->x=x+1;
  node->y=y;
  node->next=NULL;
  front->next=node;
  front=front->next;
  path[n*(x+1)+y].isowned=1;
  path[n*(x+1)+y].point=rear;
  for(i=0;i<10;i++)
  delay(10000);
  putpixel(100+20*y,120+20*x,color);
  rear->sum++;
  setsublink(rear,front,path,m,n,x+1,y);
}
if(!path[n*x+y].west)
if(!path[n*x+y-1].isowned)
{
  node=(seed*)malloc(sizeof(seed));
  node->x=x;
  node->y=y-1;
  node->next=NULL;
  front->next=node;
  front=front->next;
  path[n*x+y-1].isowned=1;
  path[n*x+y-1].point=rear;
  for(i=0;i<10;i++)
  delay(10000);
  putpixel(80+20*y,100+20*x,color);
  rear->sum++;
  setsublink(rear,front,path,m,n,x,y-1);
}
if(!path[n*x+y].east)
if(!path[n*x+y+1].isowned)
{
  node=(seed*)malloc(sizeof(seed));
  node->x=x;
  node->y=y+1;
  node->next=NULL;
  front->next=node;
  front=front->next;
  path[n*x+y+1].isowned=1;
  path[n*x+y+1].point=rear;
  for(i=0;i<10;i++)
  delay(10000);
  putpixel(120+20*y,100+20*x,color);
  rear->sum++;
  setsublink(rear,front,path,m,n,x,y+1);
}
}

void setsumlink(header*head,combinate*data)
{
header*p,*q;
int k=0;
for(p=head->next;p;p=p->next)
for(q=p->next;q;q=q->next)
{
data[k].comsum=p->sum+q->sum;
data[k].head1=p;
data[k++].head2=q;
}
}


void sortsumlink(combinate*data,int tnum)
{
int i,j;
combinate temp;
for(i=0;i<tnum;i++)
for(j=i+1;j<tnum;j++)
if(data[i].comsum<data[j].comsum)
{
  temp.comsum=data[i].comsum;
  temp.head1=data[i].head1;
  temp.head2=data[i].head2;
  data[i].comsum=data[j].comsum;
  data[i].head1=data[j].head1;
  data[i].head2=data[j].head2;
  data[j].comsum=temp.comsum;
  data[j].head1=temp.head1;
  data[j].head2=temp.head2;
}
}

待续

result* seekdoor(road*path,seed*first,header*head,int m,int n)
{
result*food;
seed*shead=first;
while(shead)
{
if(shead->x<m-1)
if(path[n*shead->x+shead->y].south)                                /*for south*/
if(path[n*(shead->x+1)+shead->y].point==head)
{
  food=(result*)malloc(sizeof(result));
  food->lx=shead->x;
  food->rx=shead->x+1;
  food->ly=shead->y;
  food->ry=shead->y;
  return food;
}
if(shead->x>0)
if(path[n*shead->x+shead->y].north)                               /*for north*/
if(path[n*(shead->x-1)+shead->y].point==head)
{
  food=(result*)malloc(sizeof(result));
  food->lx=shead->x;
  food->rx=shead->x-1;
  food->ly=shead->y;
  food->ry=shead->y;
  return food;
}
if(shead->y<n-1)
if(path[n*shead->x+shead->y].east)                              /*for east*/
if(path[n*shead->x+shead->y+1].point==head)
{
  food=(result*)malloc(sizeof(result));
  food->lx=shead->x;
  food->rx=shead->x;
  food->ly=shead->y;
  food->ry=shead->y+1;
  return food;
}
if(shead->y>0)
if(path[n*shead->x+shead->y].west)                             /*for west*/
if(path[n*shead->x+shead->y-1].point==head)
{
  food=(result*)malloc(sizeof(result));
  food->lx=shead->x;
  food->rx=shead->x;
  food->ly=shead->y;
  food->ry=shead->y-1;
  return food;
  }
shead=shead->next;
}
return NULL;
}


void opendoor(result*food)
{
int x,y,i;
y=100+(food->lx+food->rx)*10;
x=100+(food->ly+food->ry)*10;
putpixel(x,y,YELLOW);
for(i=1;i<10;i++)
{
  putpixel(x+i,y,YELLOW);
  putpixel(x-i,y,YELLOW);
  putpixel(x,y+i,YELLOW);
  putpixel(x,y-i,YELLOW);
  }
  }

本题需要一个条件
改总房间需为长方形.

我的做法是用flood fill(就是类似走迷宫的算法)求出每个区域的面积，再寻找那面墙。

那么你的大致算法是怎样的呢？
能稍微详细一点么？