BFS板子死活没找出错来

P1746 离开中山路

好玄学啊,我没看出来那里错了。qwq
by xhQYm @ 2020-04-07 15:18:44


@[kuoluo03](/user/250699) 这是我的AC代码: ``` #include<bits/stdc++.h> using namespace std; struct data { int x,y,s; }kk; queue<data> q; int n,sx,sy,fx,fy; int dx[5]={0,1,-1,0,0}; int dy[5]={0,0,0,1,-1}; char a[1001][1001]; int bj[1001][1001]={0}; void bfs(int nx,int ny) { kk.x=nx;kk.y=ny;kk.s=0; q.push(kk); while(!q.empty()) { kk=q.front(); q.pop(); // cout<<kk.x<<" "<<kk.y<<" "<<kk.s<<endl; for(int i=1;i<=4;i++) { int xx=kk.x+dx[i],yy=kk.y+dy[i]; if(xx>=1&&xx<=n&&yy>=1&&yy<=n&&a[xx][yy]=='0'&&(bj[xx][yy]>kk.s+1||!bj[xx][yy])) { if(xx==fx&&yy==fy) { cout<<kk.s+1; return; } else { data k; k.x=xx; k.y=yy; k.s=kk.s+1; bj[xx][yy]=kk.s+1; q.push(k); } } } } } int main() { cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)cin>>a[i][j]; cin>>sx>>sy>>fx>>fy; bfs(sx,sy); return 0; } ``` 希望能帮到你QWQ
by Tune_ @ 2020-04-07 15:24:52


@[lucy2008](/user/95170) 光给代码有啥用啊awa
by wpy233 @ 2020-04-07 15:25:56


@[kuoluo03](/user/250699) 这是我的AC代码: ```` #include<iostream> using namespace std; int n,fn,fm,ln,lm; int head=0,tail=0; int way[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; char a[1000][1000]; struct cc { int i,j; int step; }c[1000000]; bool b(int i,int j) { if(i>-1&&i<n&&j>-1&&j<n&&a[i][j]=='0') return true; else return false; } int main() { //init cin>>n; for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin>>a[i][j]; cin>>fn>>fm>>ln>>lm; // a[fn-1][fm-1]='1'; c[head].i=fn-1; c[head].j=fm-1; c[head].step=0; if(fn==ln&&fm==lm) { cout<<c[head].step<<endl; return 0; } while(head<=tail) { for(int i=0;i<4;i++) if(b(c[head].i+way[i][0],c[head].j+way[i][1])) { tail++; c[tail].i=c[head].i+way[i][0]; c[tail].j=c[head].j+way[i][1]; c[tail].step=c[head].step+1; a[c[tail].i][c[tail].j]='1'; //print if(c[tail].i==ln-1&&c[tail].j==lm-1) { cout<<c[tail].step<<endl; return 0; } } head++; } return 0; } ```` 希望能帮到你QWQ
by Enterprise_ @ 2020-04-07 15:33:16


大哥们别发代码啊 代码题解都有 我想知道我这个哪里错了 谢谢了!
by mot1ve @ 2020-04-07 15:34:06


@[kuoluo03](/user/250699) 你距离存的方式错了吧,不能保证最优解
by Ckger @ 2020-04-07 15:34:25


@[森蚺](/user/215590) 问题是这个连输出都没有
by mot1ve @ 2020-04-07 15:36:09


@[kuoluo03](/user/250699) 也是这个原因
by Ckger @ 2020-04-07 15:37:23


@[kuoluo03](/user/250699) 你的代码意思就是一个点只能走一次
by Ckger @ 2020-04-07 15:37:59


@[森蚺](/user/215590) 这是bfs啊大哥,而且肯定只走一次啊
by mot1ve @ 2020-04-07 15:39:21


| 下一页