NSOJ 鬼泣

今天组队赛的一道最短路的题，给你一个矩阵，矩阵上有L,R,G,A，分别表示当你到达这个点的时候你要向左，向右，向前，向后走，如果要向别的方向走需要花费1点的魔力，正常情况下走需要花费1点的时间。问花费最小魔力的时候的最少时间是多少。一个机智的处理方法是向别的方向走的时候的花费1*100000000，然后构图跑最短路出来的结果/100000000就是最小的魔力，％100000000就是最小的时间。

但是比赛的时候WA了好久，赛后RE了好久。终于发现一个严重的问题－－－－队列开小了。

平时最短路都是STL里的队列，这次用了手写的队列，然后手写的队列又没有弄成循环的队列，所以就跪了。写下来警醒自己：

手写队列要小心！！！！！

#pragma warning(disable:4996)

#include <iostream>

#include <cstring>

#include <string>

#include <vector>

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <queue>

#include <map>

#include <ctime>

using namespace std;

#define maxn 120

#define ll long long

int n, m;

int dx[4] = { 0, 1, 0, -1 };

int dy[4] = { 1, 0, -1, 0 };

const ll hcost = 100000000;

int cd(int k, char cmd){

	if (cmd == 'G') return k;

	else if (cmd == 'L') return (k + 3) % 4;

	else if (cmd == 'R') return (k + 1) % 4;

	else return (k + 2) % 4;

}

char b[maxn][maxn];

struct Edge{

	int v; ll w;

	Edge(int vi, ll wi) :v(vi), w(wi){}

	Edge(){}

};

vector<Edge> G[maxn*maxn * 8];

int getid(int i, int j, int k){

	return 4 * (i*m + j) + k;

}

bool in[maxn*maxn * 8];

ll d[maxn*maxn * 8];

bool vis[maxn*maxn * 8];

void spfa()

{

	memset(in, 0, sizeof(in));

	memset(d, 0x3f, sizeof(d));

	memset(vis, 0, sizeof(vis));

	in[0] = true; d[0] = 0;

	queue<int> que;

	que.push(0);

	while (!que.empty()){

		int u = que.front(); in[u] = false; que.pop();

		for (int i = 0; i < G[u].size(); ++i){

			int v = G[u][i].v;

			ll w = G[u][i].w;

			if (d[u] + w < d[v]){

				d[v] = d[u] + w;

				if (!in[v]) {

					que.push(v);

					in[v] = true;

				}

			}

		}

	}

}

int main()

{

	//freopen("C.in", "r", stdin);

	//freopen("out.txt", "w", stdout);

	//double t1 = clock();

	while (cin >> n >> m){

		for (int i = 0; i < n; ++i){

			scanf("%s", b[i]);

		}

		for (int i = 0; i <= n*m * 6; ++i){

			G[i].clear();

		}

		for (int i = 0; i < n; ++i){

			for (int j = 0; j < m; ++j){

				for (int k = 0; k < 4; ++k){

					int id = getid(i, j, k);

					char cmd = b[i][j];

					int cord = cd(k, cmd);

					int xx, yy;

					for (int kk = 0; kk < 4; ++kk){

						xx = i + dx[kk]; yy = j + dy[kk];

						if (!(xx >= 0 && xx < n&&yy >= 0 && yy < m)) continue;

						if (kk == cord) {

							G[id].push_back(Edge(getid(xx, yy, kk), 1LL));

						}

						else{

							G[id].push_back(Edge(getid(xx, yy, kk), hcost + 1));

						}

					}

				}

			}

		}

		spfa();

		ll ans = 1e15;

		for (int i = 0; i < 4; ++i){

			int idd = getid(n - 1, m - 1, i);

			ans = min(ans, d[idd]);

		}

		printf("%lld %lld\n", ans / hcost, ans%hcost);

	}

	//double t2 = clock();

	//cout << t2 - t1 << endl;

	return 0;

}

巴特西

NSOJ 鬼泣

最新文章

热门文章