走迷宫问题是图搜索的经典问题，这里给出两个和转弯有关的题。
Laser
原题：Laser
原题大意
有一个n×m的区域，有一个激光和一个传感器，其中有一些障碍，我们的目标就是在空白的区域放一些镜子，并且希望用最少数量的镜子，能够使激关经过反射后到达传感器。<>^v箭头指向激光的方向，C表示传感器，#表示障碍， . 表示空白区域。
算法分析
暴力模拟当前光线在何处时，放置了哪种镜子，搜下去就行了。
光线通过的路径也被视作’#’，其实这个条件是没有意义的。假若光线产生了回路，对于最优解来说与其花费更多镜子去产生回路，不如只放置一面镜子就使得方向偏转,而我们bfs出的结果一定是最优的。需要注意镜子不能摆放在起点，终点和’#’处。
程序代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int t;
int n, m;
char s[222][222];
int walk[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
int vis[222][222][4];
int pre[200000];
int cnt = 0;
struct Laser {
int x, y, turn, id, type;
} laser[200000];
bool isinit(int x, int y) {
if(s[x][y] == '>' || s[x][y] == '^' || s[x][y] == 'v' || s[x][y] == '<')
return 1;
return 0;
}
int main() {
scanf("%d", &t);
while(t--) {
memset(pre, 0, sizeof pre);
cnt = 0;
memset(vis, 0, sizeof vis);
scanf("%d%d", &n, &m);
int posx, posy, turn, edx, edy;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++) {
scanf(" %c", &s[i][j]);
if(s[i][j] == '^') turn = 0, posx = i, posy = j;
if(s[i][j] == '>') turn = 1, posx = i, posy = j;
if(s[i][j] == 'v') turn = 2, posx = i, posy = j;
if(s[i][j] == '<') turn = 3, posx = i, posy = j;
if(s[i][j] == 'C') edx = i, edy = j;
}
queue< Laser > Q;
laser[cnt++] = {posx, posy, turn, 0, -1};
vis[posx][posy][turn] = 1;
Q.push(laser[0]);
Laser res;
while(!Q.empty()) {
Laser buf = Q.front();
Q.pop();
if(buf.x == edx && buf.y == edy) {
res = buf;
break;
}
int nx, ny, nt;
for(int countup = 1; ; countup ++) {
nx = buf.x + countup * walk[buf.turn][0];
ny = buf.y + countup * walk[buf.turn][1];
if(nx >= 1 && nx <= n && ny >= 1 && ny <= m && s[nx][ny] != '#' && !isinit(nx, ny)) {
if(buf.turn == 0) {
if(!vis[nx][ny][3]) {
pre[cnt] = buf.id;
laser[cnt] = {nx, ny, 3, cnt, 0};
Q.push(laser[cnt]);
cnt++;
vis[nx][ny][3] = 1;
}
if(!vis[nx][ny][1]) {
pre[cnt] = buf.id;
laser[cnt] = {nx, ny, 1, cnt, 1};
Q.push(laser[cnt]);
cnt++;
vis[nx][ny][1] = 1;
}
} else if(buf.turn == 1) {
if(!vis[nx][ny][2]) {
pre[cnt] = buf.id;
laser[cnt] = {nx, ny, 2, cnt, 0};
Q.push(laser[cnt]);
cnt++;
vis[nx][ny][2] = 1;
}
if(!vis[nx][ny][0]) {
pre[cnt] = buf.id;
laser[cnt] = {nx, ny, 0, cnt, 1};
Q.push(laser[cnt]);
cnt++;
vis[nx][ny][0] = 1;
}
} else if(buf.turn == 2) {
if(!vis[nx][ny][1]) {
pre[cnt] = buf.id;
laser[cnt] = {nx, ny, 1, cnt, 0};
Q.push(laser[cnt]);
cnt++;
vis[nx][ny][1] = 1;
}
if(!vis[nx][ny][3]) {
pre[cnt] = buf.id;
laser[cnt] = {nx, ny, 3, cnt, 1};
Q.push(laser[cnt]);
cnt++;
vis[nx][ny][3] = 1;
}
} else if(buf.turn == 3) {
if(!vis[nx][ny][0]) {
pre[cnt] = buf.id;
laser[cnt] = {nx, ny, 0, cnt, 0};
Q.push(laser[cnt]);
cnt++;
vis[nx][ny][0] = 1;
}
if(!vis[nx][ny][2]) {
pre[cnt] = buf.id;
laser[cnt] = {nx, ny, 2, cnt, 1};
Q.push(laser[cnt]);
cnt++;
vis[nx][ny][2] = 1;
}
}
vis[nx][ny][buf.turn] = 1;
} else
break;
}
}
int step = 0;
while(!(res.x == posx && res.y == posy)) {
if(res.type == 0)
s[res.x][res.y] = '\\', step++;
else if(res.type == 1)
s[res.x][res.y] = '/', step++;
res = laser[pre[res.id]];
}
s[edx][edy] = 'C';
for(int i = 1; i <= n; i++, puts(""))
for(int j = 1; j <= m; j++)
printf("%c", s[i][j]);
}
return 0;
}
Igor and his way to work
原题大意
一座 n 行 m 列的城市。 Igor 需要找到一条从他家到单位的路径，最多转两次弯。Igor只能向左向右或是向上向下走。城市中有一些障碍，现在问你Igor是否能找到这样一条路径。
- “.” — 一个空格;
- “*” — 一个障碍;
- “S” — Igor的家;
- “T” — Igor公司所在地。
- 保证 “S” 和 “T” 都恰好出现一次。
算法分析
dfs搜索，用三维数字vis[x][y][z]，其中x，y为坐标，z为当前方向，这个数组里存的是转弯的次数，如果经过一个点的同一种方向，发现已经有比当前转向次数少的值，就说明之前已经走过，而且只用了更少的转向，所以舍弃当前值。
程序代码
#include <cstdio>
#include <cstring>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int maxn = 1000+50;
char g[maxn][maxn];
int a[maxn][maxn];
int vis[maxn][maxn][4];
int d[4][2] = {{1, 0}, {-1 ,0}, {0, 1}, {0, -1}};
int n, m;
int sx,sy,ex,ey;
void dfs(int x, int y, int pre_dir, int turns){
// if(x == 1 && y == 0) printf("%d\n", turns);
if(turns > 2 || x < 0 || x >= n || y < 0 || y >= m || g[x][y] == '*') return;
if(pre_dir >= 0 && g[x][y] == 'S') return;
if(pre_dir >=0 && vis[x][y][pre_dir] != -1)
{
if(turns >= vis[x][y][pre_dir])//不能漏了这个等号，否则会超时！！！
return;
}
if(x == ex && y == ey && turns <= 2){vis[x][y][pre_dir] = turns;return;}
for(int i = 0; i < 4; i++)
{
if(pre_dir == -1)
{
dfs(x+d[i][0], y+d[i][1],i,turns);
}
else{
vis[x][y][pre_dir] = turns;
if(pre_dir == 0){
if(i != 1)
{
if(i == pre_dir) dfs(x+d[i][0], y+d[i][1],i,turns);
else dfs(x+d[i][0], y+d[i][1],i,turns+1);
}
}
else if(pre_dir == 1){
if(i != 0)
{
if(i == pre_dir) dfs(x+d[i][0], y+d[i][1],i,turns);
else dfs(x+d[i][0], y+d[i][1],i,turns+1);
}
}
else if(pre_dir == 2){
if(i != 3)
{
if(i == pre_dir) dfs(x+d[i][0], y+d[i][1],i,turns);
else dfs(x+d[i][0], y+d[i][1],i,turns+1);
}
}
else{
if(i != 2)
{
if(i == pre_dir) dfs(x+d[i][0], y+d[i][1],i,turns);
else dfs(x+d[i][0], y+d[i][1],i,turns+1);
}
}
}
}
}
int main(){
//freopen("input.txt", "r", stdin);
scanf("%d %d", &n, &m);
for(int i = 0; i < n; i++)
scanf("%s", g[i]);
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
if(g[i][j] == 'S') sx = i, sy = j;
if(g[i][j] == 'T') ex = i, ey = j;
}
}
mem(vis,-1);
dfs(sx, sy, -1, 0);
int i;
for(i = 0; i < 4; i++)
if(vis[ex][ey][i] != -1) {printf("YES\n");break;}
if(i == 4) printf("NO\n");
return 0;
}