#include<stdio.h>
int re=0;
int seed_fill(int a[][4],int i,int j)
{
if(a[i][j]!=1) { re++;a[i][j]=1;}
if(a[i][j]==1)
return 0;
if(i>1)
seed_fill(a,i-1,j);
if(j>1)
seed_fill(a,i,j-1);
if(i<3)
seed_fill(a,i+1,j);
if(j<3)
seed_fill(a,i,j+1);
}
int main()
{
int a[][4]={{1,0,0,1},
{1,0,0,1},
{1,0,0,1}};
for(int i=0;i<12;i++)
if(a[i/4][i%4]==0)
seed_fill(a,i/4,i%4);
printf("%d\n",re);
return 0;
}
----------------解决方案--------------------------------------------------------
````````我的思路
用while读取每一行，并同时纪录两个连续*的起始和结束位置，读取下一行的时候，遇到的*进行向上探测，如果是连着的话，再把他们的面积加到一起，继续用样的循环
----------------解决方案--------------------------------------------------------
额。。。。。这个 ，我尽量不看SKD的代码把此题完成吧，但是到现在代码调试还是有错误。给我点时间，我很笨。。。。。。。。。
----------------解决方案--------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
////////////////////////////////
// Global variable
int nMap[1100][100];// Max map buff
int nMaxArea=0; // final output
int nTmax=0; // save temp max area
int nWidth=0,nHeight=0;
////////////////////////////////
// Function protocol
int SeedFill(int, int);// mian algorithm
////////////////////////////////
// mian
int main(int argc, char *argv[])
{
char ct;
FILE *in,*out;
in=fopen("satpix.in","r");
out=fopen("satpix.out","w");
// Map ini
// map description:
// 0: not usable 1: usable 2:already counted
fscanf(in,"%d%d",&nWidth,&nHeight);
printf("%d %d\n",nWidth,nHeight);
fscanf(in,"%c",&ct);// be careful of '\n'
for(int i=0;i<nHeight;i++)
for (int j=0;j<=nWidth;j++)// be careful of '\n'
{
fscanf(in,"%c",&ct);
if (ct=='.') nMap[i][j]=0;
if (ct=='*') nMap[i][j]=1;
}
//print Map
for(int i=0;i<nHeight;i++)
{
for (int j=0;j<nWidth;j++)
{
printf("%d",nMap[i][j]);
}
printf("\n");
}
// Main algorithm here
for (int i=0;i<nHeight;i++)
for (int j=0;j<nWidth;j++)
{
SeedFill(i,j);
if(nTmax>nMaxArea) nMaxArea=nTmax;
nTmax=0;
}
//print Map
printf ("\n");
for(int i=0;i<nHeight;i++)
{
for (int j=0;j<nWidth;j++)
{
printf("%d",nMap[i][j]);
}
printf("\n");
}
printf ("%d\n",nMaxArea);
fprintf(out,"%d",nMaxArea);
system("PAUSE");
fclose(in);// discard files
fclose(out);
return 0;
}
/////////////////////////////////
// Functions
int SeedFill(int width, int height)
{
// if this position is avaliable and not counted!
if (nMap[width][height]!=1) return 0;
nTmax++;//temp area +1
nMap[width][height]=2;//flag here countec
// if not the most right
if (width<(nWidth-1))
SeedFill(width+1,height);
// if not the most left
if (width>0)
SeedFill(width-1,height);
// if not the most up
if (height>0)
SeedFill(width,height-1);
// if not the most down
if (height<(nHeight-1))
SeedFill(width,height+1);
return 0;
}
[[it] 本帖最后由 SNAKEQX 于 2008-4-29 12:08 编辑 [/it]]
----------------解决方案--------------------------------------------------------
文件satpix.in
10 5
..........
**********
..........
..........
..........
按说结果是10
但是输出的是5。
----------------解决方案--------------------------------------------------------
原因找到了。
int SeedFill(int width, int height)
{
// if this position is avaliable and not counted!
if (nMap[height][width]!=1) return 0;
nTmax++;//temp area +1
//nMap[width][height]=2;这里错了，正确的在下一行
nMap[height][width]=2;
// if not the most right
if (width<(nWidth-1))
SeedFill(width+1,height);
// if not the most left
if (width>0)
SeedFill(width-1,height);
// if not the most up
if (height>0)
SeedFill(width,height-1);
// if not the most down
if (height<(nHeight-1))
SeedFill(width,height+1);
return 0;
}
但是还是不对，数组里有未被访问的区域。
我要晕了。
[[it] 本帖最后由 SNAKEQX 于 2008-4-29 13:37 编辑 [/it]]
----------------解决方案--------------------------------------------------------
搜索到０就递归．．然后把下找下一个０保证都找到
----------------解决方案--------------------------------------------------------
找到了。在这里
// Main algorithm here
for (int i=0;i<nHeight;i++)
for (int j=0;j<nWidth;j++)
{
//SeedFill(i,j);
SeedFill(j,i);
if(nTmax>nMaxArea) nMaxArea=nTmax;
nTmax=0;
}
----------------解决方案--------------------------------------------------------
终于搞定了。下面是完全的代码。
//PROG:satpix
//LANG:C++
//ID:qian.xin1
#include <stdio.h>
#include <stdlib.h>
////////////////////////////////
// Global variable
int nMap[1100][100];// Max map buff
int nMaxArea; // final output
int nTmax=0; // save temp max area
int nWidth=0,nHeight=0;
////////////////////////////////
// Function protocol
int SeedFill(int, int);// mian algorithm
////////////////////////////////
// mian
int main(int argc, char *argv[])
{
char ct;
FILE *in,*out;
in=fopen("satpix.in","r");
out=fopen("satpix.out","w");
// Map ini
// map description:
// 0: not usable 1: usable 2:already counted
fscanf(in,"%d%d",&nWidth,&nHeight);
printf("%d %d\n",nWidth,nHeight);
fscanf(in,"%c",&ct);// be careful of '\n'
for(int i=0;i<nHeight;i++)
for (int j=0;j<=nWidth;j++)
{
fscanf(in,"%c",&ct);
if (ct=='.') nMap[i][j]=0;
if (ct=='*') nMap[i][j]=1;
}
// Main algorithm here
for (int i=0;i<nHeight;i++)
for (int j=0;j<nWidth;j++)
{
SeedFill(j,i);
if(nTmax>nMaxArea) nMaxArea=nTmax;
nTmax=0;
}
fprintf(out,"%d\n",nMaxArea);
fclose(in);// discard files
fclose(out);
return 0;
}
/////////////////////////////////
// Functions
int SeedFill(int width, int height)
{
// if this position is avaliable and not counted!
if (nMap[height][width]!=1) return 0;
nTmax++;//temp area +1
nMap[height][width]=2;//flag here counted
// if not the most right
if (width<(nWidth-1))
SeedFill(width+1,height);
// if not the most left
if (width>0)
SeedFill(width-1,height);
// if not the most up
if (height>0)
SeedFill(width,height-1);
// if not the most down
if (height<(nHeight-1))
SeedFill(width,height+1);
return 0;
}
----------------解决方案--------------------------------------------------------
ANALYSIS MODE
Submit solutions for your own enjoyment.
Evaluating 'satpix'---------------------
* Compiling C++ program satpix
> Compile: OK
* Executing
> View Test Data:
Run #1 Run #3 Run #5 Run #7 Run #9 Run #11
Run #2 Run #4 Run #6 Run #8 Run #10
> Run 1: OK [0.000 secs, 3272 KB]
> Run 2: OK [0.011 secs, 3272 KB]
> Run 3: OK [0.000 secs, 3272 KB]
> Run 4: OK [0.000 secs, 3268 KB]
> Run 5: OK [0.000 secs, 3268 KB]
> Run 6: OK [0.011 secs, 3272 KB]
> Run 7: OK [0.000 secs, 3272 KB]
> Run 8: OK [0.022 secs, 3268 KB]
> Run 9: OK [0.011 secs, 3272 KB]
> Run 10: OK [0.022 secs, 3272 KB]
> Run 11: OK [0.032 secs, 5060 KB]
Analysis mode: Program NOT saved for grading.
acm给的反馈。
----------------解决方案--------------------------------------------------------