User586768 @ 2023-07-14 20:32:03
#include <bits/stdc++.h>
using namespace std;
int n=0,a[1001][1001],vis[1001][1001];
int xx1,yy1,xx2,yy2,sum[10000000];
void dfs(int x,int y,int ex,int ey,int s){
vis[x][y]=1;
if(x!=0&&vis[x-1][y]==0){
dfs(x-1,y,ex,ey,s+1);
}
if(y!=0&&vis[x][y-1]==0){
dfs(x,y-1,ex,ey,s+1);
}
if(x!=n-1&&vis[x+1][y]==0){
dfs(x+1,y,ex,ey,s+1);
}
if(y!=n-1&&vis[x][y+1]==0){
dfs(x,y+1,ex,ey,s+1);
}
if(x==ex&&y==ey){
sum[vis[1001][1001]]==s;
vis[1001][1001]++;
return;
}
}
int main(){
scanf("%d",&n);
memset(vis,0,sizeof(vis));
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
char c;
scanf("%c",&c);
a[i][j]=c-'0';
if(a[i][j]==1){
vis[i][j]=1;
}
}
}
scanf("%d %d %d %d",&xx1,&xx2,&yy1,&yy2);
int ans;
for(int i=0;i<10000000;i++){
ans=max(ans,sum[i]);
}
printf("%d",ans);
return 0;
}
by mediocre_ @ 2023-07-15 13:26:12
@zk123bc dfs肯定T啊,不对,你连代码都是错的
by mediocre_ @ 2023-07-15 13:26:44
@zk123bc 建议bfs
by User586768 @ 2023-07-16 18:13:07
@Mr_Huang12 bfs不会写
by mediocre_ @ 2023-07-16 18:41:43
@zk123bc 可以参考一下我的代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1000 + 9;
const int fx[] = {-1, 0, 0, 1};
const int fy[] = {0, -1, 1, 0};
int n, sx, sy, bx, by;
int a[N][N];
int vis[N][N];
bool use[N][N];
struct Node {
int x, y;
};
queue <Node>q;
bool inmap(int nx, int ny) {
return nx >= 1 && nx <= n && ny >= 1 && ny <= n;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
scanf("%1d", &a[i][j]);
scanf("%d%d%d%d", &sx, &sy, &bx, &by);
q.push(Node{sx, sy});
use[sx][sy] = true;
while (!q.empty()) {
Node u = q.front();
q.pop();
for (int d = 0; d < 4; ++d) {
int nx = u.x + fx[d];
int ny = u.y + fy[d];
if (inmap(nx, ny) && a[nx][ny] == 0 && !use[nx][ny]) {
vis[nx][ny] = vis[u.x][u.y] + 1;
use[nx][ny] = true;
q.push(Node{nx, ny});
}
}
}
printf("%d", vis[bx][by]);
return 0;
}
by mediocre_ @ 2023-07-16 18:43:34
@zk123bc 像这种最短路的问题最好用bfs,不然很容易T
by User586768 @ 2023-07-18 20:47:48
@Mr_Huang12 但我是全wa,没t额
by User586768 @ 2023-07-18 20:48:29
@Mr_Huang12 我再想想bfs吧