3368016_ac_16ms_388k.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

int n, m;
char map[100][100];
int visited[100][100];
typedef pair <int, int> type;
queue <type> que;
int sti, stj;
int edi, edj;
int prev[100][100];

const int mov[][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
const char dir[] = "WENS";

bool valid(int x, int y)
{
	return x >= 0 && x < n && y >= 0 && y < m && map[x][y] != '.' && visited[x][y] == 0;
}

void bfs()
{
	prev[sti][stj] = -1;
	memset(visited, 0, sizeof(visited));
	visited[sti][stj] = 1;
	que.push(make_pair(sti, stj));

	while (!que.empty())
	{
		type t = que.front();
		que.pop();
		int x = t.first;
		int y = t.second;
		for (int i = 0; i < 4; i++)
		{
			int tx = x + mov[i][0];
			int ty = y + mov[i][1];
			if (valid(tx, ty))
			{
				visited[tx][ty] = 1;
				prev[tx][ty] = i;
				que.push(make_pair(tx, ty));
				if (map[tx][ty] == 'S')
				{
					return ;
				}
			}
		}
	}
}

int main()
{
	scanf("%d%d", &n, &m);
	n = (n << 1) - 1;
	m = (m << 1) - 1;
	for (int i = 0; i < n; i++)
	{
		scanf("%s", map[i]);
		for (int j = 0; map[i][j]; j++)
		{
			if (map[i][j] == 'E')
			{
				sti = i;
				stj = j;
			}
			if (map[i][j] == 'S')
			{
				edi = i;
				edj = j;
			}
		}
	}
	bfs();
	vector <char> ans;
	ans.clear();
	while (prev[edi][edj] != -1)
	{
		int t = prev[edi][edj];
		ans.push_back(dir[t]);
		edi -= mov[t][0];
		edj -= mov[t][1];
	}
	for (int i = 0; i < ans.size(); i++)
	{
		int cnt = 0;
		int j = i;
		while (j < ans.size() && ans[j] == ans[i])
		{
			j++;
			cnt++;
		}
		printf("%c %d\n",ans[i], cnt / 2);
		i = j - 1;
	}
	return 0;
}