http://ac.nbutoj.com/Problem/view.xhtml?id=1424
-
[1424] 金克拉与贪吃蛇的故事
- 时间限制: 1000 ms 内存限制: 65535 K
- 问题描述
-
金克拉。金克拉，亩产一千八。。。——题目编号：1029(内附金克拉音乐一首)
最近Miku酱不种水果啦，因为水果不好赚钱啊。——题目编号：1140
所以就开始种起金克拉了。
贪吃蛇又来啦，最近也盯上了金克拉，是口味变了么还是说鸡鸭有禽流感不敢吃了？——题目编号：1098
Do you know Chihuo?——吃货专题(1200——1207)
这次，Miku酱找了一块 M * N 的农田，然后在里面种起了金克拉。
但是她知道这样子会被贪吃蛇全部吃掉的。所以除了金克拉，农田里还有Miku为了防止贪吃蛇吃掉农作物而造的泥土堆。但是Miku天性善良，不能让贪吃蛇饿死啊，所以就没有用泥土堆把所有金克拉都包围，而是随机的在农田里摆放泥土堆。这样子，大家都可以生存下去了酱酱酱酱~~~
- 输入
-
输入第一行包括两个正整数 M 和 N (1 <= M, N <= 100)。
接下来 M 行，每行 N 个数字，只包含 '0' 和 '1'。'0'代表这个位置种着农作物，'1'表示这个位置是泥土堆。 - 输出
-
输出能幸存下来的金克拉的数量。
- 样例输入
-
3 4 0110 1001 0110
- 样例输出
-
2
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#pragma warning(disable : 4996)
#define MAX 105
char map[MAX][MAX];
int n, m;
int ans;
bool flag;
const int moves[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
void dfs(int x, int y)
{
if(x == 1 || x == n || y == 1 || y == m)
{
flag = false;
return;
}
ans++;
for(int i = 0; i < 4; i++)
{
int p = x + moves[i][0];
int q = y + moves[i][1];
if(p >= 1 && p <= n && q >= 1 && q <= m && map[p][q] == '0')
{
map[p][q] = '1';
dfs(p, q);
}
}
}
int main()
{
freopen("in.txt", "r", stdin);
int sum = 0;
while(cin >> n >> m)
{
sum = 0;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
cin >> map[i][j];
}
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
if(map[i][j] == '0')
{
flag = true;
map[i][j] = '1';
ans = 0;
dfs(i, j);
if(flag)
{
sum += ans;
}
}
}
}
cout << sum << endl;
}
return 0;
}从第1、n行，第1、m列搜索。
改过的代码：
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#pragma warning(disable : 4996)
#define MAX 105
char map[MAX][MAX];
int n, m;
int ans;
const int moves[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
void dfs(int x, int y)
{
map[x][y] = '1';
ans++;
for(int i = 0; i < 4; i++)
{
int p = x + moves[i][0];
int q = y + moves[i][1];
if(p >= 1 && p <= n && q >= 1 && q <= m && map[p][q] == '0')
{
dfs(p, q);
}
}
}
int main()
{
//freopen("in.txt", "r", stdin);
int sum = 0;
while(cin >> n >> m)
{
sum = 0;
ans = 0;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
cin >> map[i][j];
if(map[i][j] == '0')
{
sum++;
}
}
}
for(int i = 1; i <= m; i++)
{
if(map[1][i] == '0')
{
dfs(1, i);
//cout << ans << endl;
}
if(map[n][i] == '0')
{
dfs(n, i);
//cout << ans << endl;
}
}
for(int j = 1; j <= n; j++)
{
if(map[j][1] == '0')
{
dfs(j, 1);
//cout << ans << endl;
}
if(map[j][m] == '0')
{
dfs(j, m);
//cout << ans << endl;
}
}
cout << sum - ans << endl;
}
return 0;
}
其实代码1，只要去掉递归的终止条件就可以AC的
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define MAX 105
char map[MAX][MAX];
int n, m;
int ans;
bool flag;
const int moves[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
void dfs(int x, int y)
{
if(x == 1 || x == n || y == 1 || y == m)
{
flag = false;
//return;
}
ans++;
for(int i = 0; i < 4; i++)
{
int p = x + moves[i][0];
int q = y + moves[i][1];
if(p >= 1 && p <= n && q >= 1 && q <= m && map[p][q] == '0')
{
map[p][q] = '1';
dfs(p, q);
}
}
}
int main()
{
//freopen("in.txt", "r", stdin);
int sum = 0;
while(cin >> n >> m)
{
sum = 0;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
cin >> map[i][j];
}
}
for(int i = 2; i <= n- 1; i++)
{
for(int j = 2; j <= m - 1; j++)
{
if(map[i][j] == '0')
{
flag = true;
map[i][j] = '1';
ans = 0;
dfs(i, j);
if(flag)
{
sum += ans;
}
}
}
}
cout << sum << endl;
}
return 0;
}