XDOJ 相鄰區域（序號71）題解
題目如下：
一個n行m列的矩陣被劃分成t個矩形區域，分別用數字1-t來標識，同一個區域內的元素都用同一個數字標識，如下圖所示，一個6行8列的矩陣被分成8個矩形區域，分別用編號1-8標識，當兩個小區域之間公用一條邊時，稱這兩個區域相鄰，例如下圖中區域5的相鄰區域有6個，分別為1,2,3,6,7,8，但4并不是它的相鄰區域，請寫一個程式找出區域k的所有相鄰區域，
輸入說明：
輸入第一行為四個整數n，m， t，k，整數之間用空格分隔，n表示矩陣行數（n<20），m表示矩陣列數（m<20），t表示矩陣被劃分為t個矩形區域（0<t<50），k為其中某個區域的編號（1<=k<=t），接下來是n行資料，每行m個整數，表示矩陣內各個元素所在的區域，整數之間用空格分開，
輸出說明：
輸出為一個整數，表示與k相鄰的區域個數，
輸入樣例
6 8 8 5
1 1 2 2 2 3 3 4
1 1 2 2 2 3 3 4
1 1 2 2 2 3 3 4
1 1 5 5 5 5 5 6
1 1 5 5 5 5 5 6
7 7 7 7 7 8 8 8
輸出樣例
6
這個題目很好理解，就是給你一坨二維陣列，將其分為了t個矩形塊，并且替你標好了編號，指定一個編號，讓你找到所有與目標矩形塊相鄰的矩形塊，并輸出矩形塊的數量，
關鍵點如下：
- 所有區塊均是矩形塊，這一點大大減少了代碼量以及思考量
- 因為是矩形塊，我們只需要找到目標編號的矩形的四個頂點的位置，就能確定目標位置
- 確定四個頂點之后，只需要對目標矩形塊相鄰的上下左右四個邊的資料進行回圈判斷其編號型別即可
代碼如下：（因為XDer統一學C，所以就貼C了）
#include<stdio.h>
int main()
{
int m,n;
scanf("%d%d",&n,&m);//讀入行，列
int a[n][m];
int i,j,k,t;
int x,y=0;
scanf("%d%d",&t,&k);//讀入總矩形塊數目和目標編號
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
scanf("%d",&a[i][j]);
}
}
int flag1=-1,flag2=-1,flag3=-1,flag4=-1;//1是左上角，2是右上角，3是左下角，4是右下角
for(i=0;i<n;i++)//確定兩個頂點
{
for(j=0;j<m;j++)
{
if(a[i][j]==k)
{
flag1=j;
flag3=i;
break;
}
}
if(flag1!=-1)
break;
}
for(i=0;i<n;i++)//確定右上角
{
for(j=0;j<m;j++)
{
if(a[i][j]==k)
{
if(j+1==m||a[i][j+1]!=k)
{
flag2=j;
break;
}
}
}
if(flag2!=-1)
break;
}
for(i=0;i<n;i++)//確定右下角
{
for(j=0;j<m;j++)
{
if(a[i][j]==k)
{
if(i+1==n||a[i+1][j]!=k)
{
flag4=i;
break;
}
}
}
if(flag4!=-1)
break;
}
int b[t+1];//定義一個新的陣列b，作為標記陣列，如果對矩形塊四邊回圈時出現了對應編號的代碼，則標記為1
for(i=0;i<t+1;i++)//變數陣列不能在定義時賦值，所以單獨賦值
{
b[i]=0;
}
for(i=flag1;i<=flag2;i++)//回圈上邊
{
if(flag3==0)
break;
else
{
x=a[flag3-1][i];
b[x]=1;
}
}
for(i=flag1;i<=flag2;i++)//回圈下邊
{
if(flag4+1==n)
break;
else
{
x=a[flag4+1][i];
b[x]=1;
}
}
for(i=flag3;i<=flag4;i++)//回圈左邊
{
if(flag1==0)
break;
else
{
x=a[i][flag1-1];
b[x]=1;
}
}
for(i=flag3;i<=flag4;i++)//回圈右邊
{
if(flag2+1==m)
break;
else
{
x=a[i][flag2+1];
b[x]=1;
}
}
for(i=0;i<t+1;i++)對b陣列進行加法，結果即為相鄰區域的數目
{
y+=b[i];
}
printf("%d",y);
return 0;
}
代碼中小細節有很多，還需要自行學習，我不再一一贅述，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/241386.html
標籤：其他