Yannik @ 2023-07-17 16:08:07
#include<bits/stdc++.h>
#define N 510
using namespace std;
int n,m,x11,x22,y11,y22,g[N][N];
int dist[N][N];
bool vis[N][N];
int dx[4]= {-1,0,1,0};
int dy[4]= {0,-1,0,1};
struct node {
int x,y;
};
void spfa(int xx,int yy) {
queue<node> q;
q.push({xx,yy});
dist[xx][yy]=0;
vis[xx][yy]=1;
queue<int> last;
last.push(-1);
while(q.size()) {
node t=q.front();
q.pop();
vis[t.x][t.y]=0;
for(int i=0; i<4; i++) {
int a=t.x+dx[i];
int b=t.y+dy[i];
if(a<1||a>n||b<1||b>n) continue;
int w=0;
int l=last.front();
if(g[a][b]==g[t.x][t.y]&&g[a][b]==1) {
int l=last.front();
if(a==t.x&&b!=t.y&&l!=1) {
w=1;
} else if(a!=t.x&&b==t.y&&l!=0) {
w=1;
} else if(a==t.x&&b!=t.y&&l==1) {
w=0;
} else if(a!=t.x&&b==t.y&&l==0) {
w=0;
}
}
if(dist[a][b]>dist[t.x][t.y]+w&&g[a][b]==g[t.x][t.y]&&g[a][b]==1) {
dist[a][b]=dist[t.x][t.y]+w;
if(!vis[a][b]) {
vis[a][b]=1;
q.push({a,b});
}
if(a==t.x&&b!=t.y&&l!=1) {
last.push(1);
} else if(a!=t.x&&b==t.y&&l!=0) {
last.push(0);
} else if(a==t.x&&b!=t.y&&l==1) {
last.push(1);
} else if(a!=t.x&&b==t.y&&l==0) {
last.push(0);
}
}
}
last.pop();
}
}
int main() {
memset(dist,0x3f,sizeof dist);
cin>>n;
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
char c;
cin>>c;
if(c=='x') {
g[i][j]=0;
} else if(c=='A') {
g[i][j]=1;
x11=i,y11=j;
} else if(c=='B') {
g[i][j]=1;
x22=i,y22=j;
} else {
g[i][j]=1;
}
}
}
spfa(x11,y11);
if(dist[x22][y22]!=0x3f3f3f3f) {
cout<<dist[x22][y22]-1;
} else {
cout<<"-1";
}
return 0;
}by MUNCR7 @ 2023-07-17 16:30:41
#include<bits/stdc++.h>
using namespace std;
int m,n,x1,x2;
int yy1,yy2,k,flag=1e6;
char a[1001][1001];
int xx[]= {1,-1,0,0};
int yy[]= {0,0,1,-1};
int walk[1011][1001];
void dfs(int x,int y,int lx,int ly,int cnt)
{
if(cnt>flag)return ;
if(x==x2&&y==yy2)
{
flag=min(flag,cnt);
}
for(int i=0; i<4; i++)
{
int tx=x+xx[i],ty=y+yy[i];
if(tx>=0&&tx<m&&ty>=0&&ty<n&&walk[tx][ty]==0&&a[tx][ty]!='x')
{
walk[tx][ty]=1;
if(lx==-114514)dfs(tx,ty,xx[i],yy[i],cnt);
else if(lx==xx[i]&&ly==yy[i])dfs(tx,ty,xx[i],yy[i],cnt);
else dfs(tx,ty,xx[i],yy[i],cnt+1);
walk[tx][ty]=0;
}
}
}
int main()
{
cin >> m ;
n=m;
for(int i=0; i<m; i++)
{
for(int j=0; j<n; j++)
{
cin >> a[i][j];
if(a[i][j]=='A')
{
x1=i;
yy1=j;
}
if(a[i][j]=='B')
{
x2=i;
yy2=j;
}
}
}
dfs(x1,yy1,-114514,0,0);
if(flag==1e6)cout <<-1;
else cout <<flag;
return 0;
}by MUNCR7 @ 2023-07-17 16:31:14
这个是AC代码
by JERRYXY @ 2023-07-17 16:31:16
if(dist[a][b]>dist[t.x][t.y]+w&&g[a][b]==g[t.x][t.y]&&g[a][b]==1)应改为
if(dist[a][b]>=dist[t.x][t.y]+w&&g[a][b]==g[t.x][t.y]&&g[a][b]==1)因为先出现不一定最优
但这样会超时
所以要在前面加上结束判断（但我也不知道怎么改:(）
by 2224_22_xmx @ 2023-07-17 16:31:52
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N = 110;
int n;
char g[N][N];
int dist[N][N];
bool vis[N][N];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
struct node {
int x, y;
};
void spfa(int xx, int yy) {
queue<node> q;
q.push({xx, yy});
dist[xx][yy] = 0;
vis[xx][yy] = 1;
queue<int> last;
last.push(-1);
while (q.size()) {
node t = q.front();
q.pop();
vis[t.x][t.y] = 0;
for (int i = 0; i < 4; i++) {
int a = t.x + dx[i];
int b = t.y + dy[i];
if (a < 0 || a >= n || b < 0 || b >= n) continue;
int w = 0;
int l = last.front();
if (g[a][b] == g[t.x][t.y] && g[a][b] == 'x') {
if (a == t.x && b != t.y && l != 1) {
w = 1;
} else if (a != t.x && b == t.y && l != 0) {
w = 1;
} else if (a == t.x && b != t.y && l == 1) {
w = 0;
} else if (a != t.x && b == t.y && l == 0) {
w = 0;
}
}
if (dist[a][b] > dist[t.x][t.y] + w && g[a][b] == g[t.x][t.y] && g[a][b] == 'x') {
dist[a][b] = dist[t.x][t.y] + w;
if (!vis[a][b]) {
vis[a][b] = 1;
q.push({a, b});
}
if (a == t.x && b != t.y && l != 1) {
last.push(1);
} else if (a != t.x && b == t.y && l != 0) {
last.push(0);
} else if (a == t.x && b != t.y && l == 1) {
last.push(1);
} else if (a != t.x && b == t.y && l == 0) {
last.push(0);
}
}
}
last.pop();
}
}
int main() {
memset(dist, 0x3f, sizeof dist);
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> g[i][j];
}
}
int x11, y11, x22, y22;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (g[i][j] == 'A') {
x11 = i, y11 = j;
}
if (g[i][j] == 'B') {
x22 = i, y22 = j;
}
}
}
spfa(x11, y11);
if (dist[x22][y22] != 0x3f3f3f3f) {
cout << dist[x22][y22] - 1 << endl;
} else {
cout << "-1" << endl;
}
return 0;
}
这是ChatGPT的答案