目前也是发现同一个状态他走了多次。
```cpp
#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
using namespace std;
struct Node{
int x,y,qwq;
char c;
Node()=default;
explicit Node(int x,int y,char c,int qwq) : x(x),y(y),c(c),qwq(qwq) {}
};
int change(char c){
if (c=='E'){
return 1;
}
if (c=='S'){
return 2;
}
if (c=='W'){
return 3;
}
return 4;
}
int main(){
int n,m;
cin >> n >> m;
vector<vector<int>> maze(n+10,vector<int>(m+10,0));
vector<vector<vector<bool>>> st(n+10,vector<vector<bool>>(n+10,vector<bool>(5,false)));
int t;
for (int i=1;i<=n;++i){
for (int j=1;j<=m;++j){
scanf("%d",&t);
if (t==1){
maze[i][j]=maze[i][j+1]=maze[i+1][j]=maze[i+1][j+1]=1;
}
}
}
++n,++m;
unordered_map<char,pair<char,char>> m1;
unordered_map<char,pair<int,int>> m2;
m1['E']={'N','S'},m1['W']={'N','S'},m1['N']={'E','W'},m1['S']={'E','W'};
m2['N']={-1,0},m2['S']={1,0},m2['E']={0,1},m2['W']={0,-1};
queue<Node> q;
int x1,y1,x2,y2;
cin >> x1 >> y1 >> x2 >> y2;
char c;
cin >> c;
q.emplace(x1+1,y1+1,c,0);
st[x1+1][y1+1][change(c)]=true;
++x2,++y2;
++n,++m;
int x,y,qwq,tx,ty;
int cnt=20;
while (!q.empty() && cnt--){
x=q.front().x,y=q.front().y,qwq=q.front().qwq;
c=q.front().c;
q.pop();
cout<<x<<" "<<y<<" "<<c<<endl;
if (x==x2 && y==y2){
cout<<qwq<<endl;
return 0;
}
++qwq;
if (st[x][y][change(m1[c].first)]==false){
q.emplace(x,y,m1[c].first,qwq);
st[x][y][change(m1[c].first)]=true;
}
if (st[x][y][change(m1[c].second)]==false){
q.emplace(x,y,m1[c].second,qwq);
st[x][y][change(m1[c].second)]=true;
}
q.emplace(x,y,m1[c].second,qwq);//转弯
for (int i=1;i<=3;++i){//直走
tx=x+m2[c].first*i,ty=y+m2[c].second*i;
if (tx<=0 || tx>n || ty<=0 || ty>m){
continue;
}
if (maze[tx][ty]==1){
break;
}
if (st[tx][ty][change(c)]==false){
//cout<<tx<<" "<<ty<<" "<<st[tx][ty][change(c)]<<endl;
st[tx][ty][change(c)]=true;
q.emplace(tx,ty,c,qwq);
}
}
}
cout<<-1<<endl;
return 0;
}
```
by xiaoyang222 @ 2024-03-31 14:30:52
目前发现了
``q.emplace(x,y,m1[c].second,qwq);//转弯``
有问题了,把这一行删掉就没有重复了,但是越界了,就很奇怪
by xiaoyang222 @ 2024-03-31 14:33:13
越界找到了,是 `++n,++m;` 了两次
by xiaoyang222 @ 2024-03-31 14:39:34
好了,是80分了
```cpp
#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
using namespace std;
struct Node{
int x,y,qwq;
char c;
Node()=default;
explicit Node(int x,int y,char c,int qwq) : x(x),y(y),c(c),qwq(qwq) {}
};
int change(char c){
if (c=='E'){
return 1;
}
if (c=='S'){
return 2;
}
if (c=='W'){
return 3;
}
return 4;
}
int main(){
int n,m;
cin >> n >> m;
vector<vector<int>> maze(n+2,vector<int>(m+2,0));
vector<vector<vector<bool>>> st(n+2,vector<vector<bool>>(m+2,vector<bool>(5,false)));
int t;
for (int i=1;i<=n;++i){
for (int j=1;j<=m;++j){
scanf("%d",&t);
if (t==1){
maze[i][j]=maze[i][j+1]=maze[i+1][j]=maze[i+1][j+1]=1;
}
}
}
unordered_map<char,pair<char,char>> m1;
unordered_map<char,pair<int,int>> m2;
m1['E']={'N','S'},m1['W']={'N','S'},m1['N']={'E','W'},m1['S']={'E','W'};
m2['N']={-1,0},m2['S']={1,0},m2['E']={0,1},m2['W']={0,-1};
queue<Node> q;
int x1,y1,x2,y2;
cin >> x1 >> y1 >> x2 >> y2;
char c;
cin >> c;
q.emplace(x1+1,y1+1,c,0);
st[x1+1][y1+1][change(c)]=true;
++x2,++y2;
++n,++m;
int x,y,qwq,tx,ty;
while (!q.empty()){
x=q.front().x,y=q.front().y,qwq=q.front().qwq;
c=q.front().c;
q.pop();
if (x==x2 && y==y2){
cout<<qwq<<endl;
return 0;
}
++qwq;
if (st[x][y][change(m1[c].first)]==false){
q.emplace(x,y,m1[c].first,qwq);
st[x][y][change(m1[c].first)]=true;
}
if (st[x][y][change(m1[c].second)]==false){
q.emplace(x,y,m1[c].second,qwq);
st[x][y][change(m1[c].second)]=true;
}
for (int i=1;i<=3;++i){//直走
tx=x+m2[c].first*i,ty=y+m2[c].second*i;
if (tx<=0 || tx>n || ty<=0 || ty>m){
continue;
}
if (maze[tx][ty]==1){
break;
}
if (st[tx][ty][change(c)]==false){
//cout<<tx<<" "<<ty<<" "<<st[tx][ty][change(c)]<<endl;
st[tx][ty][change(c)]=true;
q.emplace(tx,ty,c,qwq);
}
}
}
cout<<-1<<endl;
return 0;
}
```
by xiaoyang222 @ 2024-03-31 14:40:35
#3 数据是:
```
6 7
0 0 0 0 0 0 0
0 0 0 0 1 0 0
0 0 1 0 0 0 0
0 0 1 0 0 0 0
0 0 0 0 0 1 0
0 0 0 0 0 0 0
1 1 1 6 E
```
输出:
```
11
```
但我输出
```
7
```
by xiaoyang222 @ 2024-03-31 14:42:07
90pts了:
```cpp
#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
using namespace std;
struct Node{
int x,y,qwq;
char c;
Node()=default;
explicit Node(int x,int y,char c,int qwq) : x(x),y(y),c(c),qwq(qwq) {}
};
int change(char c){
if (c=='E'){
return 1;
}
if (c=='S'){
return 2;
}
if (c=='W'){
return 3;
}
return 4;
}
int main(){
int n,m;
cin >> n >> m;
vector<vector<int>> maze(n+2,vector<int>(m+2,0));
vector<vector<vector<bool>>> st(n+2,vector<vector<bool>>(m+2,vector<bool>(5,false)));
int t;
for (int i=1;i<=n;++i){
for (int j=1;j<=m;++j){
scanf("%d",&t);
if (t==1){
maze[i][j]=maze[i][j+1]=maze[i+1][j]=maze[i+1][j+1]=1;
}
}
}
unordered_map<char,pair<char,char>> m1;
unordered_map<char,pair<int,int>> m2;
m1['E']={'N','S'},m1['W']={'N','S'},m1['N']={'E','W'},m1['S']={'E','W'};
m2['N']={-1,0},m2['S']={1,0},m2['E']={0,1},m2['W']={0,-1};
queue<Node> q;
int x1,y1,x2,y2;
cin >> x1 >> y1 >> x2 >> y2;
char c;
cin >> c;
q.emplace(x1+1,y1+1,c,0);
st[x1+1][y1+1][change(c)]=true;
++x2,++y2;
++n,++m;
int x,y,qwq,tx,ty;
while (!q.empty()){
x=q.front().x,y=q.front().y,qwq=q.front().qwq;
c=q.front().c;
q.pop();
if (x==x2 && y==y2){
cout<<qwq<<endl;
return 0;
}
++qwq;
if (st[x][y][change(m1[c].first)]==false){
q.emplace(x,y,m1[c].first,qwq);
st[x][y][change(m1[c].first)]=true;
}
if (st[x][y][change(m1[c].second)]==false){
q.emplace(x,y,m1[c].second,qwq);
st[x][y][change(m1[c].second)]=true;
}
for (int i=1;i<=3;++i){//直走
tx=x+m2[c].first*i,ty=y+m2[c].second*i;
if (tx<=1 || tx>n || ty<=1 || ty>m){
continue;
}
if (maze[tx][ty]==1){
break;
}
if (st[tx][ty][change(c)]==false){
//cout<<tx<<" "<<ty<<" "<<st[tx][ty][change(c)]<<endl;
st[tx][ty][change(c)]=true;
q.emplace(tx,ty,c,qwq);
}
}
}
cout<<-1<<endl;
return 0;
}
```
#8 是:
```
20 20
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 1 1 0 1 1 0 0 1 1 1 0 1 1 1
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
19 4 15 17 E
```
答案是:
```
33
```
但是我输出了:
```
11
```
by xiaoyang222 @ 2024-03-31 15:46:26
过了,同学帮我调了
by xiaoyang222 @ 2024-03-31 16:04:37