[题面] https://www.luogu.org/problemnew/show/P4289
题目描述:
在一个 4*4 的方框内摆放了若干个相同的玩具, 某人想将这些玩具重新摆放成为他心中理想的状态, 规定移动时只能将玩具向上下左右四个方向移动, 并且移动的位置不能有玩具, 请你用最少的移动次数将初始的玩具状态移动到某人心中的目标状态.
输入输出格式:
输入格式:
前 4 行表示玩具的初始状态, 每行 4 个数字 1 或 0,1 表示方格中放置了玩具, 0 表示没有放置玩具. 接着是一个空行. 接下来 4 行表示玩具的目标状态, 每行 4 个数字 1 或 0, 意义同上.
输出格式:
一个整数, 所需要的最少移动次数.
输入输出样例:
- Input:
- 1111
- 0000
- 1110
- 0010
- 1010
- 0101
- 1010
- 0101
- Output:
- 4
[题解]
调试了 1 小时迭代加深, 最后还是滚回去写 BFS 了...
普通的 BFS 很好写, 这里直接放代码了:
- #include
- #include
- using namespace std;
- const int dx[5]={0,0,0,1,-1};
- const int dy[5]={0,1,-1,0,0};
- int goal[5][5];
- const int n=4;
- struct state{int board[5][5];int step;}start;
- inline bool is_finished(state tmp)
- {
- register int i,j;
- for(i=1;i<=n;i++)
- for(j=1;j<=n;j++)
- if(goal[i][j]!=tmp.board[i][j])return 0;
- return 1;
- }
- inline int BFS()
- {
- queueQ;
- Q.push(start);
- while(!Q.empty())
- {
- state now=Q.front();
- Q.pop();
- if(is_finished(now))return now.step;
- register int i,j,k;
- for(i=1;i<=n;i++)
- for(j=1;j<=n;j++)
- for(k=1;k<=4;k++)
- {
- if(i+dx[k]>n||j+dy[k]>n||i+dx[k]<1||j+dy[k]<1)continue;
- if(now.board[i][j]==now.board[i+dx[k]][j+dy[k]])continue;
- swap(now.board[i][j],now.board[i+dx[k]][j+dy[k]]);
- now.step ++;
- Q.push(now);
- now.step --;
- swap(now.board[i][j],now.board[i+dx[k]][j+dy[k]]);
- }
- }
- }
- int main()
- {
- register int i,j;
- start.step=0;
- for(i=1;i<=n;i++)
- for(j=1;j<=n;j++)
- {
- char tmp;cin>>tmp;
- start.board[i][j]=(tmp=='0')?0:1;
- }
- for(i=1;i<=n;i++)
- for(j=1;j<=n;j++)
- {
- char tmp;cin>>tmp;
- goal[i][j]=(tmp=='0')?0:1;
- }
- cout<<BFS()<<endl;
- return 0;
- }
但是...... 评测结果 https://www.luogu.org/recordnew/show/16067080 却不容乐观.
MLE!!!
原来, 在 BFS 的过程中, 一些状态是被重复枚举的.
如何判重?
注: 用 map 判重的效果并不容乐观, 笔者亲测 https://www.luogu.org/recordnew/show/16067156 .
看得出来, 输入都由 0 和 1 组成, 那么, 我们可以将状态压缩.
没事,\(2^{16}=65535\), 数组放的下.
定义: vis[S] 表示到达状态 \(S\) 的最短步数.
那么判重就简单多了.
- Code:
- #include
- #include
- #include
- using namespace std;
- const int dx[5]={0,0,0,1,-1};
- const int dy[5]={0,1,-1,0,0};
- const int n=4;
- bool goal[5][5];
- int vis[65536];
- struct state{bool board[5][5];int step;}start;
- queueQ;
- inline bool is_finished(state tmp)
- {
- register int i,j;
- for(i=1;i<=n;i++)
- for(j=1;j<=n;j++)
- if(goal[i][j]^tmp.board[i][j])return 0;
- return 1;
- }
- inline int change(state tmp)
- {
- register int i,j;
- int res=0;
- for(i=1;i<=n;i++)
- for(j=1;j<=n;j++)
- res=(res<<1)|tmp.board[i][j];
- return res;
- }
- inline int BFS()
- {
- memset(vis,0x3f3f3f3f,sizeof(vis));
- Q.push(start);
- while(!Q.empty())
- {
- state now=Q.front();
- Q.pop();
- if(is_finished(now))return now.step;
- int BIN=change(now);
- if(vis[BIN]<=now.step)continue;
- vis[BIN]=now.step;
- register int i,j,k;
- for(i=1;i<=n;i++)
- for(j=1;j<=n;j++)
- for(k=1;k<=4;k++)
- {
- if(i+dx[k]>n||j+dy[k]>n||i+dx[k]<1||j+dy[k]<1)continue;
- if(now.board[i][j]==now.board[i+dx[k]][j+dy[k]])continue;
- swap(now.board[i][j],now.board[i+dx[k]][j+dy[k]]);
- now.step ++;
- Q.push(now);
- now.step --;
- swap(now.board[i][j],now.board[i+dx[k]][j+dy[k]]);
- }
- }
- return -1;
- }
- int main()
- {
- register int i,j;
- start.step=0;
- for(i=1;i<=n;i++)
- for(j=1;j<=n;j++)
- {
- char tmp;cin>>tmp;
- start.board[i][j]=(tmp=='0')?0:1;
- }
- for(i=1;i<=n;i++)
- for(j=1;j<=n;j++)
- {
- char tmp;cin>>tmp;
- goal[i][j]=(tmp=='0')?0:1;
- }
- cout<<BFS()<<endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2945041.html