wa_wa_wa_wa @ 2024-07-10 13:32:34
#include<bits/stdc++.h>
using namespace std;
int n,m;
struct node{
int x,y;
};
int a[1005][1005],vis[1005][1005],anss[1005][1005];
const int movex[4][2] = {{0,1},{0,-1},{-1,0},{1,0}};
int main(){
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++){
string s;
cin >> s;
for(int j = 0; j < n; j++){
a[i][j+1] = s[j]-'0';
}
}
int s[2];
s[0] = 1;
s[1] = 0;
while(m--){
queue<node>q;
queue<node>q2;
int x,y;
scanf("%d%d",&x,&y);
if(anss[x][y]){
printf("%d\n",anss[x][y]);
continue;
}
memset(vis,0,sizeof(vis));
q.push((node){x,y});
vis[x][y] = 1;
int ans = 1;
while(q.size()){
node tmp = q.front();
q.pop();
for(int i = 0;i < 4; i++){
int xx = tmp.x+movex[i][0];
int yy = tmp.y+movex[i][1];
if(xx > n || xx < 1 || yy > n || yy < 1 || vis[xx][yy] || a[xx][yy] != s[a[tmp.x][tmp.y]]){
continue;
}
ans++;
vis[xx][yy] = 1;
q.push((node){xx,yy});
q2.push((node){xx,yy});
}
}
anss[x][y] = ans;
while(q2.size()){
anss[q2.front().x][q2.front().y] = ans;
q2.pop();
}
printf("%d\n",ans);
}
return 0;
}by Jokersheng @ 2024-07-11 10:08:34
你参考一下
by wa_wa_wa_wa @ 2024-07-11 10:32:50
已AC，蟹蟹各位大佬
by Jokersheng @ 2024-07-11 10:36:38
@wa_wa_wa_wa 你最后迷宫那道(L**)的```cpp
using namespace std;
int n,m,sx,sy,ex,ey;
int dx[8]={-1,1,0,0,-1,1,-1,1},dy[8]={0,0,-1,1,-1,1,1,-1};//偏移量
char mp[16385][8005];
struct node{
int x,y,s;
};
bool check(int xx,int yy){
return xx>=1&&xx<=n&&yy>=1&&yy<=m;
}
bool look(int mx,int my){
if(mx==ex&&my==ey)return true;
for(int i=0;i<8;i++){
int ux=mx+dx[i],uy=my+dy[i];
while(check(ux,uy)&&mp[ux][uy]=='O'){
if(ux==ex&&uy==ey)return true;
ux+=dx[i],uy+=dy[i];
}
}
return false;
}
void bfs(){
int mk[n+1][m+1]={0};
memset(mk,0,sizeof(mk));
queue<node> q;
q.push((node){sx,sy,0});
while(q.size()){
int xx=q.front().x,yy=q.front().y,ss=q.front().s;
if(look(xx,yy)){
printf("%d\n",ss);
return;
}
for(int i=0;i<4;i++){
int px=xx+dx[i],py=yy+dy[i];
if(check(px,py)&&mk[px][py]==0&&mp[px][py]=='O'){
q.push((node){px,py,ss+1});
mk[px][py]=1;
}
}
q.pop();
}
printf("Poor Harry\n");
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>mp[i][j];
scanf("%d%d%d%d",&ex,&ey,&sx,&sy);
while(!(sx==0&&sy==0&&ex==0&&ey==0)){
bfs();
scanf("%d%d%d%d",&ex,&ey,&sx,&sy);
}
return 0;
}