H、 Chino with Ciste

广度优先搜索，求最少拐弯次数。

https://ac.nowcoder.com/acm/contest/553/H

遍历一个点的四个方向时，将这个方向上所有可走的点都加到队列里面，并且标记的时候多标记一维方向。

Code：

#include <bits/stdc++.h>
#define ll long long
const ll mod = 1e9 + 7;
using namespace std;
char s[2005][2005];
bool book[2005][2005][4];
struct node
{
	int x;
	int y;
	int cnt;
	node(int xx, int yy,int ccnt) {
		x = xx;
		y = yy;
		cnt = ccnt;
	}
};
int dir[4][2] = { 1,0,0,1,-1,0,0,-1 };
queue<node>q;
int main()
{
	int n, m, sx, sy;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
	{
		scanf("%s", s[i] + 1);
		for (int j = 1; j <= m; j++)
		{
			if (s[i][j] == 'S')
			{
				sx = i;
				sy = j;
			}
		}
	}
	q.push(node{ sx,sy,0 });
	book[sx][sy][0] = book[sx][sy][1] = book[sx][sy][2] = book[sx][sy][3] = true;
	while (!q.empty())
	{
		node temp = q.front();
		q.pop();
		for (int k = 0; k < 4; k++)
		{
			int tx = temp.x;
			int ty = temp.y;
			while (true)
			{
				tx += dir[k][0];
				ty += dir[k][1];
				if (tx<1 || tx>n || ty<1 || ty>m || book[tx][ty][k] == true)
					break;
				if (s[tx][ty] == '.')
				{
					book[tx][ty][k] = true;
					q.push(node{ tx,ty,temp.cnt + 1 });
				}
				else if (s[tx][ty] == 'T')
				{
					printf("%d", temp.cnt);
					return 0;
				}
				else
					break;
			}
		}
	}
	printf("troil");
}
/*
7 9
.....***.
.***.***.
.*...***.
.*.*****.
.*.......
S..*....T
*.......*
*/