狗狗40题搞完纪念 » 1009

1009
1009.cpp


#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 64;
const int MAXQ = 50 * 50 * 50;

int x[MAXQ], y[MAXQ], z[MAXQ];
int d[MAXN][MAXN][MAXN];
char e[MAXN][MAXN];

int main() {
	int n, p1, p2, p3, ans;

	while (scanf("%d%d%d%d", &n, &p1, &p2, &p3) != EOF && n > 0) {
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				scanf(" %c", &e[i][j]);
				for (int k = 0; k < n; ++k) {
					d[i][j][k] = -1;
				}
			}
		}

		ans = -1;
		d[p1 - 1][p2 - 1][p3 - 1] = 0;
		x[0] = p1 - 1;
		y[0] = p2 - 1;
		z[0] = p3 - 1;
		for (int begin = 0, end = 1; begin < end; ++begin) {
			p1 = x[begin];
			p2 = y[begin];
			p3 = z[begin];
		//	printf("%d %d %d\n", p1, p2, p3);
			if (p1 == p2 && p2 == p3) {
				ans = d[p1][p2][p3];
				break;
			}
			for (int i = 0; i < n; ++i) {
				if (e[p1][i] == e[p2][p3] && d[i][p2][p3] == -1) {
					d[i][p2][p3] = d[p1][p2][p3] + 1;
					x[end] = i;
					y[end] = p2;
					z[end] = p3;
					++end;
				}
			}
			for (int i = 0; i < n; ++i) {
				if (e[p2][i] == e[p3][p1] && d[p1][i][p3] == -1) {
					d[p1][i][p3] = d[p1][p2][p3] + 1;
					x[end] = p1;
					y[end] = i;
					z[end] = p3;
					++end;
				}
			}
			for (int i = 0; i < n; ++i) {
				if (e[p3][i] == e[p1][p2] && d[p1][p2][i] == -1) {
					d[p1][p2][i] = d[p1][p2][p3] + 1;
					x[end] = p1;
					y[end] = p2;
					z[end] = i;
					++end;
				}
			}
		}

		if (ans == -1) {
			puts("impossible");
		} else {
			printf("%d\n", ans);
		}
	}

	return 0;
}

//Run ID  	Submit Time  	Judge Status  	Problem ID  	Language  	Run Time(ms)  	Run Memory(KB)  	User Name  	Admin
//252 	2010-06-24 17:13:47 	Accepted 	1009 	C++ 	30 	2672 	anotherpeg 	Source
One Response to “1009”
  1. sshic says:

    把所有i点到j点的最短距离遍历出来,再求3个点到某个相同点的最小距离之和,这样可行吗?

  2.  
Leave a Reply