先声明一下,我一开始没注意难度,结果干了三个小时(别管我是怎么做到的)也没弄出来...... 先上代码(总感觉比大多数题解都短,但是思路应该没问题啊......)
#include <iostream>
using namespace std;
const int maxl=1511;
int n,m,sx,sy,flag=0;
int vis[maxl][maxl];
char a[maxl][maxl];
int copy1[8][2]={{0,m},{0,2*m},{n,0},{2*n,0},{n,m},{2*n,2*m},{n,2*m},{2*n,m}};
int move[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
void bfs(int x,int y){
int head = 0, tail = 1;
int q[maxl][2];
q[0][0] =x;
q[0][1]=y;
vis[x][y]=1;
while(head < tail){
int p[2]={};
p[0]=q[head++][0];
p[1]=q[head][1];
if (p[0]!=(p[0]%n)&&p[1]!=(p[1]%m)){
flag=1;
return;
}
for(int i = 0; i < 4; i++){
if((a[p[0]][p[1]]=='.'||a[p[0][p[1]]=='S')&& vis[p[0]][p[1]] == 0){
q[tail++][0]=p[0]+move[i][0];
q[tail][1]=p[1]+move[i][1];
vis[p[0]+move[i][0]][p[1]+move[i][1]]=1;
}
}
}
return;
}
int main(){
cin>>n>>m;
int a[n][m]={};
for (int i=0;i<n;i++){
for (int j=0;j<m;j++){
cin>>a[i][j];
if (a[i][j]=='S'){
sx=i;sy=j;
}
}
}
for (int b=0;b<8;b++){
for (int i=0;i<n;i++){
for (int j=0;j<m;j++){
a[i+copy1[b][0]][j+copy1[b][1]]=a[i][j];
}
}
}
sx+=n;sy+=m;
bfs(sx,sy);
if (flag==1) cout<<"Yes";
else cout<<"No";
}
其实思路是把几个题解揉起来:3*3复制迷宫矩阵(@revenger),然后通过比较原坐标和取模n,m之后的坐标搞出来(@DEVILK)。 结果有点悲惨...... 不方便截图,总之4个压根没输出6个搞反了,最后全体WA...... 请问哪位可以解释一下?