NYOJ-题目27 水池数目

青旅半醒 2022-08-25 05:29 173阅读 0赞

[http://acm.nyist.net/JudgeOnline/problem.php?pid=27][http_acm.nyist.net_JudgeOnline_problem.php_pid_27]

程序代码（一）：时间 8 内存 272

\#include

\#define N 102

\#define M 102

int map\[N\]\[M\] = \{0\};

void search(int i,int j) //递归调用，将是 1 的 连续地方 全部 变为 0

if(map\[i\]\[j-1\]) \{ map\[i\]\[j-1\]=0; search(i,j-1); \}

if(map\[i\]\[j+1\]) \{ map\[i\]\[j+1\]=0; search(i,j+1); \}

if(map\[i-1\]\[j\]) \{ map\[i-1\]\[j\]=0; search(i-1,j); \}

if(map\[i+1\]\[j\]) \{ map\[i+1\]\[j\]=0; search(i+1,j); \}

int main()

int t,n,m;

int i,j,count;

scanf("%d",&t);

while(t--)

scanf("%d %d",&n,&m);

count=0;

for(i=1;i<=n;i++)

for(j=1;j<=m;j++)

scanf("%d",&map\[i\]\[j\]);

for(i=1;i<=n;i++)

for(j=1;j<=m;j++)

if(map\[i\]\[j\])

count++;

map\[i\]\[j\]=0;

search(i,j);

printf("%d\\n",count);

return 0;

程序代码（二）：时间 4 内存 308

\#include

int map\[100\]\[100\],vis\[100\]\[100\]; //这里定义两个数组同时搜索，时间少，但消耗内存大

int n,m;

void dfs(int i,int j)

vis\[i\]\[j\]=1;

if(map\[i-1\]\[j\]&&!vis\[i-1\]\[j\])

vis\[i-1\]\[j\]=1;

dfs(i-1,j);

if(map\[i+1\]\[j\]&&!vis\[i+1\]\[j\])

vis\[i+1\]\[j\]=1;

dfs(i+1,j);

if(map\[i\]\[j-1\]&&!vis\[i\]\[j-1\])

vis\[i\]\[j-1\]=1;

dfs(i,j-1);

if(map\[i\]\[j+1\]&&!vis\[i\]\[j+1\])

vis\[i\]\[j+1\]=1;

dfs(i,j+1);

int main()

int i,j,sum,t;

scanf("%d",&t);

while(t--)

scanf("%d%d",&m,&n);

memset(vis,0,sizeof(vis));

memset(map,0,sizeof(map));

for(i=1;i<=m;i++)

for(j=1;j<=n;j++)

scanf("%d",&map\[i\]\[j\]);

sum=0;

for(i=1;i<=m;i++)

for(j=1;j<=n;j++)

if(!vis\[i\]\[j\]&&map\[i\]\[j\])

sum++;

dfs(i,j);

printf("%d\\n",sum);

return 0;

程序代码（三）：时间 0 内存 248

\#include

char map\[100\]\[100\],vis\[100\]\[100\]; //这里把数组定义成字符型数组，来存放整型数，减少了内现存和时间

int n,m;

void dfs(int i,int j)

vis\[i\]\[j\]=1;

if(map\[i-1\]\[j\]&&!vis\[i-1\]\[j\])

vis\[i-1\]\[j\]=1;

dfs(i-1,j);

if(map\[i+1\]\[j\]&&!vis\[i+1\]\[j\])

vis\[i+1\]\[j\]=1;

dfs(i+1,j);

if(map\[i\]\[j-1\]&&!vis\[i\]\[j-1\])

vis\[i\]\[j-1\]=1;

dfs(i,j-1);

if(map\[i\]\[j+1\]&&!vis\[i\]\[j+1\])

vis\[i\]\[j+1\]=1;

dfs(i,j+1);

int main()

int i,j,sum,t;

scanf("%d",&t);

while(t--)

scanf("%d%d",&m,&n);

memset(vis,0,sizeof(vis));

memset(map,0,sizeof(map));

for(i=1;i<=m;i++)

for(j=1;j<=n;j++)

scanf("%d",&map\[i\]\[j\]);

sum=0;

for(i=1;i<=m;i++)

for(j=1;j<=n;j++)

if(!vis\[i\]\[j\]&&map\[i\]\[j\])

sum++;

dfs(i,j);

printf("%d\\n",sum);

return 0;

[http_acm.nyist.net_JudgeOnline_problem.php_pid_27]: http://acm.nyist.net/JudgeOnline/problem.php?pid=27

NYOJ-题目27 水池数目

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关 NYOJ 题目854 留恋

相关 NYOJ-题目27 水池数目

相关 NYOJ—题目88 找球号(一）

相关 NYOJ-题目221 Tree

相关 NYOJ - 汉诺塔（三）

相关 NYOJ—88 汉诺塔（一）

相关 NYOJ-467 中缀式变后缀式

相关过河问题--nyoj题目47

相关水池的数目

相关 NYOJ-78-圈水池