SRM 706 div 1

发表于 | 更新于

p1

Limak is a little bear. He is currently planning a walk on a rectangular grid. Each cell of the grid is either empty or it contains a single candy. Empty cells are denoted '.', cells with a candy are denoted '#'. Limak wants to go from the top-left corner to the bottom-right corner of the grid. Since he loves sweets, there should be a candy in each cell he visits, including the starting and the final cell. He can only move in the four cardinal directions. In other words, he can move from cell A directly to cell B if and only if A and B share a side. You are given the vector t: the current state of the grid. Limak's journey may be impossible on the current grid. Your task is to make it possible by moving as few candies as you can. Moving a candy means picking it up and placing it into any empty cell. Return the smallest number of candies that have to be moved in order to make Limak's journey possible. If there is no solution, return -1 instead.

Solution

好吧，又不会做了， 棋盘上可以从左上到右下DP。 然而这个是各个方向都能走的，所以好像可以求最短路？但也不会建图 发现正解是按照走的步数划分阶段的 这个很厉害啊，棋盘上的最优新解法get。 还有一点，这个题拿哪些不需要管，只要走就行了，最后肯定能构造出一组可行解来

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
#define put(x) printf("%d",x)
#define foreach(it,x) for(typeof((x).begin()) it=(x).begin();it!=(x).end();++it)
#define iter(x) typeof((x).begin())
#define riter(x) typeof((x).rbegin())
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
using std::vector;
using std::string;
const int dx[4]={0,0,-1,1},dy[4]={1,-1,0,0},MAXN=30;
struct MovingCandies
{
	int minMoved(vector<string> t)
	{
		static int f[MAXN][MAXN][MAXN<<1];
		int res=0;
		static char map[MAXN][MAXN];
		int n=t.size(),m=t[0].size(),cct=0;
		for(int i=1;i<=n;++i)
			for(int j=1;j<=m;++j)
			{
				map[i][j]=t[i-1][j-1];
				if(map[i][j]=='#') ++cct;
			}
		if(cct<n+m-1) return -1;
		memset(f,31,sizeof(f));res=0x1f1f1f1f;
		f[1][1][0]=map[i][j]=='.';
		for(int st=1;st<=cct-1;++st)
		{
			for(int x=1;x<=n;++x)
				for(int y=1;y<=m;++y)
				{
					int cost=map[x][y]=='.';
					for(int d=0;d<4;++d)
					{
						int nx=x+dx[d],ny=y+dy[d];
						if(!(1<=nx && nx<=n && 1<=ny && ny<=m)) continue;
						chkmn(f[x][y][st],f[nx][ny][st-1]+cost);
					}
				}
			chkmn(res,f[n][m][st]);
		}	
		return res;
	}
};