题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1054
由于数据范围只有4*4
所以我们直接想到暴力bfs，从起始的状态一步一步走
只有0和1，就可以用一个16位的二进制数来表示一个状态
哈希一下就好了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
#include<bits/stdc++.h> using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(!isdigit(c)){if(c=='-')y=-y;c=getchar();} while(isdigit(c))x=x*10+c-'0',c=getchar(); return x*y; } struct node{ int now,num; node(int _,int __){now=_,num=__;} node(){} }; int mp[10][10]; bool vis[500050]; int tox[4]={-1,0,1,0}; int toy[4]={0,1,0,-1}; inline int zip(){ int ret=0; for(int i=1; i<=4; i++){ for(int j=1; j<=4; j++){ ret<<=1; ret|=mp[i][j]; } } return ret; } void unzip(int x){ for(int i=4; i>=1; i--){ for(int j=4; j>=1; j--){ mp[i][j]=x&1; x>>=1; } } } int bfs(int s,int t){ if(s==t)return 0; queue<node>q; q.push(node(s,0)); vis[s]=true; while(!q.empty()){ node tmp=q.front(); int now=tmp.now; int num=tmp.num; q.pop(); unzip(now); for(int i=1; i<=4; i++){ for(int j=1; j<=4; j++){ if(mp[i][j]){ for(int k=0; k<4; k++){ int x=i+tox[k],y=j+toy[k]; if(mp[x][y] || x<1 || x>4 || y<1 || y>4)continue; mp[x][y]=1; mp[i][j]=0; int to=zip(); if(!vis[to]){ vis[to]=true; q.push(node(to,num+1)); if(to==t)return num+1; } mp[i][j]=1; mp[x][y]=0; } } } } } } int main(){ char op[10]; for(int i=1; i<=4; i++){ scanf("%s",op+1); for(int j=1; j<=4; j++)mp[i][j]=op[j]-'0'; } int s=zip(); for(int i=1; i<=4; i++){ scanf("%s",op+1); for(int j=1; j<=4; j++)mp[i][j]=op[j]-'0'; } int t=zip(); printf("%d\n",bfs(s,t)); return 0; } |
