怎么查找到矩陣中連續挨著的1的塊,并回傳座標和1的個數.PS中的魔術棒為什么會找的那么快,求大神掃盲.
uj5u.com熱心網友回復：
僅供參考：//試題編號：0186
//海龜圈地
//難度級別：D； 運行時間限制：1000ms； 運行空間限制：51200KB； 代碼長度限制：2000000B
//試題描述
// 海龜小蠻在沙灘上趾高氣揚地走來走去，并且蠻橫地宣布：“凡我足跡所到之處均為本海龜的領地。”
// 海龜的任何行動均可分解為下面三個基本動作：
// f 向前爬一格
// l 原地左轉90度
// r 原地右轉90度
// 由于小蠻不允許別的海龜經過它的領地，所以，由它足跡圍成的封閉區域也就都成了它的領地。
// 你的任務是編程式根據檔案輸入的小蠻的一系列基本動作，計算出小蠻共霸占了多少格的領地。
// 程式檔案主名為turtle。
// 為加深對題意的理解，我們觀察下面的基本動作序列：
// flffflfffrfrrffflf
// 小蠻在出發點當然會留下足跡#，如果把它開始的方向設為向下，可以把它的足跡（用*標出的位置）畫成下面的示意圖：
// ****
// * *
// # *
// ****
// 顯然，小蠻的領地總數為15格。
//輸入
// 其中只有一個長度不超過1000的字串，且該字串不包含'f'、'l'、'r'之外的字符。
//輸出
// 其中只有一個正整數，即領地總格數。
//輸入示例
// flffflfffrfrrffflf
//輸出示例
// 15
//其他說明
// 2011年北京市海淀區中學組賽題
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 1000
static char n[2*MAXN+2][2*MAXN+2];//記錄某處被爬過資訊:0未爬過|1爬過
char f;//當前方向'N'|'S'|'W'|'E'
int x,y;//當前位置
char p[MAXN+1];
int i,L;
int a,b,h,t;
int sp=0;
int x1[MAXN];
int x2[MAXN];
int y1[MAXN];
int yy1,xx1,xx2;
void push(int ay1,int ax1,int ax2) {
y1[sp]=ay1;
x1[sp]=ax1;
x2[sp]=ax2;
if (sp<MAXN-1) {
sp=sp+1;
} else {
printf("stack overflow!\n");
exit(1);
}
}
void pop(void) {
sp=sp-1;
yy1=y1[sp];
xx1=x1[sp];
xx2=x2[sp];
}
//void show() {
// int zy,zx;
//
// for (zy=0;zy<2*MAXN+2;zy++) {
// for (zx=0;zx<2*MAXN+2;zx++) {
// printf("%d",n[zy][zx]);
// }
// printf("\n");
// }
// printf("\n");
//}
void scanlinefill() {
int xx,ax1,ax2;
while (1) {
if (sp<=0) break;//
pop();
// printf("O yy1,xx1,xx2=%d,%d,%d\n",yy1,xx1,xx2);
for (xx=xx1;xx<=xx2;xx++) n[yy1][xx]=2;//填充本條線
yy1++;
if (yy1<=2*MAXN)
for (xx=xx1;xx<=xx2;xx++) {//從左往右考查緊挨下面一條線各點
if (n[yy1][xx ]==0) {
ax1=xx-1;
while (1) {//向左找非0點
if (n[yy1][ax1]!=0) break;
ax1--;
}
ax1++;//非0點右邊為新掃描線左點
}
if (n[yy1][xx ]==0) {
ax2=xx+1;
while (1) {//向右找非0點
if (n[yy1][ax2]!=0) break;
ax2++;
}
ax2--;//非0點左邊為新掃描線右點
// printf("I yy1,ax1,ax2=%d,%d,%d\n",yy1,ax1,ax2);
push(yy1,ax1,ax2);//記錄新掃描線到堆疊中
xx=ax2+1;//下次回圈從該新掃描線右點的右邊開始考查
}
}
}
}
int main() {
scanf("%s",p);
f='S';
y=MAXN;
x=MAXN;
n[y][x]=1;
L=strlen(p);
for (i=0;i<L;i++) {
switch (p[i]) {
case 'f':
switch (f) {
case 'N':y--;n[y][x]=1;break;
case 'S':y++;n[y][x]=1;break;
case 'W':x--;n[y][x]=1;break;
case 'E':x++;n[y][x]=1;break;
}
break;
case 'l':
switch (f) {
case 'N':f='W';break;
case 'S':f='E';break;
case 'W':f='S';break;
case 'E':f='N';break;
}
break;
case 'r':
switch (f) {
case 'N':f='E';break;
case 'S':f='W';break;
case 'W':f='N';break;
case 'E':f='S';break;
}
break;
}
}
// show();
for (y=0;y<2*MAXN+2;y++) {n[y][0]=2;n[y ][2*MAXN+1]=2;}
for (x=0;x<2*MAXN+2;x++) {n[0][x]=2;n[2*MAXN+1][x ]=2;}
// show();
push(1,1,2*MAXN);//從(y1==1,x1==1,x2==2*MAXN)開始
scanlinefill();//往下使用掃描線種子填充演算法填充2
// show();
a=0;
for (y=0;y<2*MAXN+1;y++) {
for (x=0;x<2*MAXN+1;x++) {
if (n[y][x]!=2) a++;
}
}
printf("%d\n",a);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/188303.html
標籤：C++ 語言
上一篇：如何判斷陣列的某一位物件被填充了