> #include <iostream>
> #include <vector>
> using namespace std;
> 
> const int Vam = 5000;
> const int INF = 1 << 20;
> 
> const int px[4] = { -1,0,0,1 };
> const int py[4] = { 0,-1,1,0 };
> 
> struct Situ
> {
> 	int x;
> 	int y;
> 	int d;
> }que[150];
> bool serched[14][14];
> 
> vector<int> G[Vam];
> int match[Vam];
> bool used[Vam];
> 
> void add_edge(int u, int w);
> bool dfs(int v);
> 
> int X, Y, X_Y;
> 
> int room[14][14];
> int roomnum[14][14];
> int pnum, dnum;
> int mindistance[150][50];
> 
> bool bfs(int sx, int sy);
> 
> int main()
> {
> 	int casen, st, p;
> 	char ch;
> 	bool flag;
> 
> 	cin >> casen;
> 
> 	while (casen--)
> 	{
> 		pnum = 0;
> 		dnum = 0;
> 		st = 0;
> 
> 		for (int i = 0; i < 14; i++)
> 		{
> 			for (int j = 0; j < 14; j++)
> 			{
> 				room[i][j] = 0;
> 				roomnum[i][j] = 0;
> 			}
> 		}
> 
> 		for (int i = 0; i < 150; i++)
> 		{
> 			for (int j = 0; j < 50; j++)
> 			{
> 				mindistance[i][j] = INF;
> 			}
> 		}
> 
> 		for (int i = 0; i < Vam; i++)
> 		{
> 			G[i].clear();
> 			match[i] = -1;
> 			used[i] = false;
> 		}
> 
> 		cin >> X >> Y;
> 		X_Y = X * Y;
> 
> 		for (int i = 1; i <= X; i++)
> 		{
> 			for (int j = 1; j <= Y; j++)
> 			{
> 				cin >> ch;
> 				switch (ch)
> 				{
> 				case '.':
> 					room[i][j] = 1;
> 					roomnum[i][j] = pnum++;
> 					break;
> 				case 'D':
> 					room[i][j] = 2;
> 					roomnum[i][j] = dnum++;
> 					break;
> 				case 'X':
> 					room[i][j] = 0;
> 					break;
> 				}
> 			}
> 		}
> 
> 		for (int i = 1; i <= X; i++)
> 		{
> 			for (int j = 1; j <= Y; j++)
> 			{
> 				if (room[i][j] == 2)
> 				{
> 					roomnum[i][j] += pnum;
> 				}
> 			}
> 		}
> 
> 		flag = false;
> 		for (int i = 2; i < X; i++)
> 		{
> 			for (int j = 2; j < Y; j++)
> 			{
> 				if (room[i][j])
> 				{
> 					if (bfs(i, j))
> 					{
> 						flag = true;
> 					}
> 				}
> 			}
> 		}
> 		if (flag)
> 		{
> 			cout << "impossible\n";
> 			continue;
> 		}
> 
> 		p = 0;
> 		for (st = 0; (st < X_Y) && (p < pnum); st++)
> 		{
> 			for (int i = 0; i < pnum; i++)
> 			{
> 				for (int j = 0; j < dnum; j++)
> 				{
> 					if (mindistance[i][j] - 1 <= st)
> 					{
> 						add_edge(i, pnum + st * dnum + j);
> 					}
> 				}
> 			}
> 
> 			for (int i = 0; i < Vam; i++)
> 			{
> 				used[i] = false;
> 			}
> 
> 			for (int i = 0; i < dnum; i++)
> 			{
> 				if (dfs(pnum + st * dnum + i))
> 				{
> 					p++;
> 				}
> 			}
> 		}
> 
> 		cout << st << '\n';
> 
> 	}
> 	return 0;
> }
> 
> void add_edge(int u, int w)
> {
> 	G[u].push_back(w);
> 	G[w].push_back(u);
> 	return;
> }
> 
> bool dfs(int v)
> {
> 	int u, w;
> 
> 	used[v] = true;
> 
> 	for (int i = 0; i < G[v].size(); i++)
> 	{
> 		u = G[v][i];
> 		w = match[u];
> 
> 		if (w < 0)
> 		{
> 			match[v] = u;
> 			match[u] = v;
> 			return true;
> 		}
> 		else if (!used[w])
> 		{
> 			if (dfs(w))
> 			{
> 				match[v] = u;
> 				match[u] = v;
> 				return true;
> 			}
> 		}
> 	}
> 
> 	return false;
> }
> 
> bool bfs(int sx, int sy)
> {
> 	static Situ m, s;
> 	int qb = 0, qf = 0;
> 	bool flag = true;
> 
> 	for (int i = 0; i < 14; i++)
> 	{
> 		for (int j = 0; j < 14; j++)
> 		{
> 			serched[i][j] = false;
> 		}
> 	}
> 
> 	s.x = sx;
> 	s.y = sy;
> 	s.d = 0;
> 
> 	que[qf++] = s;
> 
> 	while (qf > qb)
> 	{
> 		m = que[qb++];
> 
> 		for (int i = 0; i < 4; i++)
> 		{
> 			s.x = m.x + px[i];
> 			s.y = m.y + py[i];
> 			s.d = m.d + 1;
> 			if ((!serched[s.x][s.y]) && room[s.x][s.y])
> 			{
> 				serched[s.x][s.y] = true;
> 
> 				if (room[s.x][s.y] == 2)
> 				{
> 					mindistance[roomnum[sx][sy]][roomnum[s.x][s.y] - pnum] = s.d;
> 					flag = false;
> 				}
> 				else
> 				{
> 					que[qf++] = s;
> 				}
> 			}
> 		}
> 	}
> 
> 	return flag;
> }
> 
> /*
> 数据直接 Ctrl + C 复制, 再 Ctrl + V 粘贴就行
> 
> 数据:
> 
> 9
> 
> 5 5
> XDXXX
> X...X
> X.X.X
> X...X
> XXXXX
> 
> 5 12
> XXXXXXXXXXXX
> X..........D
> X.XXXXXXXXXX
> X..........X
> DDDDDDDDDDDD
> 
> 12 12
> DDDDDDDDDDDD
> D..........D
> D..........D
> D..........D
> D..........D
> D..........D
> D..........D
> D..........D
> D..........D
> D..........D
> D..........D
> DDDDDDDDDDDD
> 
> 12 12
> XXXXXXXXXXDD
> X..........X
> X.XXXXXXXXXX
> X..........X
> XXXXXXXXXX.X
> X..........X
> X.XXXXXXXXXX
> X..........X
> XXXXXXXXXX.X
> X..........X
> X.X.X.X.X..X
> XXXXXXXXXXXX
> 
> 12 12
> XXXXXXXXXXDX
> X..........D
> X.XXXXXXXXXX
> X..........X
> XXXXXXXXXX.X
> X..........X
> X.XXXXXXXXXX
> X..........X
> XXXXXXXXXX.X
> X..........X
> X.X.X.X.X..X
> XXXXXXXXXXXX
> 
> 12 12
> XXXXXXXXXXDX
> X..........D
> X.XXXXXXXXXX
> X..........D
> XXXXXXXXXX.X
> X..........X
> X.XXXXXXXXXX
> X..........X
> XXXXXXXXXX.X
> X..........X
> X.X.X.X.X..X
> XXXXXXXXXXDX
> 
> 6 6
> XDXXXX
> D....D
> X.X..X
> X.XX.X
> X...XX
> XXXDXX
> 
> 5 5
> XXXXX
> X...D
> X.XXX
> X...D
> XXXXX
> 
> 7 6
> XXXXXX
> X....D
> XXXX.X
> X....X
> X.XXXX
> X....X
> XXDXXX
> 
> 
> 结果:
> 
> 8
> 6
> 5
> 60
> 55
> 22
> 4
> 4
> 7
> 
> */

• Re:贴个c++代码, 再贴几组数据, 建议不要用数组, 不太好估计大小 (13) sf30 2020-03-03 17:32:48