格子を切る
8067 ワード
/* ， ， 60。
： m x n ， ， 。
， 。
， 0
：
m n (m,n<10)
n ， m ， 。 10000
： ， 。
：
：
3 3
10 1 52
20 30 1
1 2 3
：
3
：
：
4 3
1 1 1 1
1 30 80 2
1 1 1 100
：
10*/
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
int m, n, minStep, sum;
int dir[4][2] = {-1, 0, 0, 1, 1, 0, 0, -1};
int map[10][10];
bool vis[10][10];
bool judgeBound(int x, int y)
{
if(x<0 || x>=m || y<0 || y>=n)
return false;
return true;
}
void DFS(int x, int y, int tot, int cnt)
{
tot += map[x][y];
if(tot == sum)
{
if(cnt+1 < minStep)
minStep = cnt+1;
return;
}
if(tot > sum || cnt+1 > minStep)
return;
for(int i = 0; i < 4; ++i)
{
int tx = x + dir[i][0];
int ty = y + dir[i][1];
if(judgeBound(tx, ty) && !vis[tx][ty] && tot+map[tx][ty] <= sum)
{
vis[x][y] = true;
DFS(tx, ty, tot, cnt+1);
vis[x][y] = false;
}
}
}
int main()
{
while(~scanf("%d%d", &n, &m))
{
sum = 0;
for(int i = 0; i < m; ++i)
for(int j = 0; j < n; ++j)
{
scanf("%d", &map[i][j]);
sum += map[i][j];
}
if(sum & 1 || (map[0][0]<<1) > sum)
printf("0
");
else
{
sum >>= 1;
minStep = 0x7fffffff;
memset(vis, false, sizeof(vis));
DFS(0, 0, 0, 0);
if(minStep == 0x7fffffff)
printf("0
");
else
printf("%d
", minStep);
}
}
return 0;
}
/*
3 3
10 1 52
20 30 1
1 2 3
3
3 3
24 1 1
6 24 1
1 1 1
2
4 3
1 1 1 1
1 30 80 2
1 1 1 100
10
9 9
2 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
*/