洛谷傳送門

解析

乍一看：bfs板子題

冰法師最棒了

然鵝
看了一眼數據范圍
心中已有畫面

《面 堂 發 黑》

怎么辦嘞？

我們想到：
因為該題來與去的可逆性
我們搜一次后，這些點以后都不會再用到
而且每次覆蓋到的所有點答案都是一樣的
由于第一個結論，我們不必再費心保留原圖
由于第二個結論，我們可以用DP來解決
但熟悉bfs模板的小朋友都知道：
bfs模板中途是無法記錄都曾有哪些元素曾進隊的
（順道送個bfs模板）：

oid bfs(int x,int y){queue<int>xq;queue<int>yq;xq.push(x);yq.push(y);while(!xq.empty()){int X,Y;X=xq.front();Y=yq.front();int nx,ny;for(int i=0;i<=3;i++){nx=X+dx[i];ny=Y+dy[i];if(nx<=m&&nx&&ny<=n&&ny&&a[nx][ny]){a[nx][ny]=0;xq.push(nx);yq.push(ny);}}xq.pop();yq.pop();}return; }

解決方法1：

做一個數組存所有進過隊的元素，或者直接用指針手寫隊列
但為了顯出我們的高級 更好的代碼效率
可以使用

解決方法2：

把坐標的兩個數存進一個hash數k中
用same[i][j]=k表示(i,j)的答案與k所對應的答案相等
這樣dp只需存入起點答案，其他點用same映射即可

代碼

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<map> #include<vector> #include<queue> #include<stack> #include<deque> #include<set> #include<string> using namespace std; int a[1005][1005]; long long same[1005][1005]; long long dp[1005][1005]; int jd[1005][1005]; int m,n; int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0}; long long hash(int a,int b){return a*1331+b; } long long bfs(int x,int y){if(same[x][y]){long long b=same[x][y] % 1331;long long a=same[x][y] / 1331;return dp[a][b];}if(dp[x][y]) return dp[x][y];queue<int>xq;queue<int>yq;xq.push(x);yq.push(y);jd[x][y]=0;int tot=1;while(!xq.empty()){int X,Y;X=xq.front();Y=yq.front();int nx,ny;for(int i=0;i<=3;i++){nx=X+dx[i];ny=Y+dy[i];if(nx<=m&&nx&&ny<=m&&ny&&a[nx][ny]+a[X][Y]==1&&jd[nx][ny]){jd[nx][ny]=0;same[nx][ny]=hash(x,y);tot++;xq.push(nx);yq.push(ny);}}//a[X][Y]=-10;xq.pop();yq.pop();}return dp[x][y]=tot; } int main(){int t,r;scanf("%d%d",&m,&n);for(int i=1;i<=m;i++){for(int j=1;j<=m;j++){scanf("%1d",&a[i][j]);dp[i][j]=same[i][j]=0;jd[i][j]=1;}}for(int i=1;i<=n;i++){scanf("%d%d",&t,&r);printf("%lld\n",bfs(t,r));} return 0; }

AC快樂！！！

（點贊評論了解一下qwq）

總結

以上是生活随笔為你收集整理的bfs：01迷宫（洛谷P1141）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。