思維,暴力,最短路,搜尋
P1979 華容道
題目描述
小\(B\)最近迷上了華容道，可是他總是要花很長的時間才能完成一次。于是，他想到用程式設計來完成華容道：給定一種局面， 華容道是否根本就無法完成，如果能完成， 最少需要多少時間。
小\(B\)玩的華容道與經典的華容道遊戲略有不同，遊戲規則是這樣的：
在一個\(n \times m\)棋盤上有\(n \times m\)個格子，其中有且隻有一個格子是空白的，其餘\(n \times m-1\)個格子上每個格子上有一個棋子，每個棋子的大小都是\(1 \times 1\)的；
有些棋子是固定的，有些棋子則是可以移動的；
任何與空白的格子相鄰（有公共的邊）的格子上的棋子都可以移動到空白格子上。
遊戲的目的是把某個指定位置可以活動的棋子移動到目标位置。
給定一個棋盤，遊戲可以玩\(q\)次，當然，每次棋盤上固定的格子是不會變的， 但是棋盤上空白的格子的初始位置、 指定的可移動的棋子的初始位置和目标位置卻可能不同。第\(i\)次玩的時候， 空白的格子在第\(EX_i\)行第\(EY_i\)列，指定的可移動棋子的初始位置為第\(SX_i\)行第\(SY_i\)列，目标位置為第\(TX_i\)行第\(TY_i\)列。
假設小\(B\)每秒鐘能進行一次移動棋子的操作，而其他操作的時間都可以忽略不計。請你告訴小 B 每一次遊戲所需要的最少時間，或者告訴他不可能完成遊戲。
輸入輸出格式
輸入格式：
第一行有\(3\)個整數，每兩個整數之間用一個空格隔開，依次表示\(n,m,q\)；
接下來的\(n\)行描述一個\(n \times m\)的棋盤，每行有\(m\)個整數，每兩個整數之間用一個空格隔開，每個整數描述棋盤上一個格子的狀态， \(0\)表示該格子上的棋子是固定的，\(1\) 表示該格子上的棋子可以移動或者該格子是空白的。
接下來的\(q\)行，每行包含 \(6\) 個整數依次是 \(EX_i,EY_i,SX_i,SY_i,TX_i,TY_i\)，每兩個整數之間用一個空格隔開，表示每次遊戲空白格子的位置，指定棋子的初始位置和目标位置。
輸出格式：
共\(q\)行，每行包含\(1\)個整數，表示每次遊戲所需要的最少時間，如果某次遊戲無法完成目标則輸出\(−1\) 。
說明
對于 \(30\%\)的資料， \(1 ≤ n, m ≤ 10,q = 1\)；
對于 \(60\%\) 的資料， \(1 ≤ n, m ≤ 30,q ≤ 10\)；
對于 \(100\%\) 的資料， \(1 ≤ n, m ≤ 30,q ≤ 500\) 。
對于我這種弱水準的選手，一定要好好練部分分。
注意到我們可以在每次遊戲枚舉空白點位置和操作點位置進行搜尋，則複雜度為\(O(n^2m^2q)\)，在考場上想不到正解時，一定要把這部分分拿到。
在洛谷神機下拿了80分，事實上應該隻有60分
60~80pts
#include <cstdio>
#include <queue>
using namespace std;
const int N=32;
int g[N][N],n,m,vis[N][N][N][N],q;
int ex,ey,sx,sy,tx,ty,t,ans;
const int dx[5]={0,-1,0,1,0};
const int dy[5]={0,0,1,0,-1};
int abs(int x){return x>0?x:-x;}
struct node
{
int x0,y0,x1,y1,step;
node(int x0,int y0,int x1,int y1,int step)
{
this->x0=x0;this->y0=y0;this->x1=x1;this->y1=y1;this->step=step;
}
};
void bfs()
{
queue <node > q;
node st(ex,ey,sx,sy,0);
q.push(st);
while(!q.empty())
{
int x0=q.front().x0,y0=q.front().y0,x1=q.front().x1,y1=q.front().y1,step=q.front().step;
if(x1==tx&&y1==ty) {ans=step;return;}
q.pop();
if(vis[x0][y0][x1][y1]==t) continue;
vis[x0][y0][x1][y1]=t;
if(x0==x1&&abs(y0-y1)==1)
{
node tt(x0,y1,x1,y0,step+1);
q.push(tt);
}
if(y0==y1&&abs(x0-x1)==1)
{
node tt(x1,y0,x0,y1,step+1);
q.push(tt);
}
for(int i=1;i<=4;i++)
{
int X=x0+dx[i],Y=y0+dy[i];
if(g[X][Y]&&(X!=x1||Y!=y1))
{
node tt(X,Y,x1,y1,step+1);
q.push(tt);
}
}
}
}
int main()
{
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&g[i][j]);
for(t=1;t<=q;t++)
{
scanf("%d%d%d%d%d%d",&ex,&ey,&sx,&sy,&tx,&ty);
ans=-1;bfs();
printf("%d\n",ans);
}
return 0;
}
代碼也不長
後來胡亂搞了搞A*結果比暴力還慢，表示不會。。
考慮正解，我們發現如果我們要移動的那個點要移動，則必須帶着空白一起移動，否則沒有意義。
每次詢問，我們可以先把空白移到初始點旁邊再說，對之後的狀态，一定是點帶空白走
對于原圖的每個位置的點，它可以帶四個方向的空白，于是把它拆成四個點建圖。
邊為拆的四個點互相進行連邊權值要求，和空白與點交換的邊權1，可以在詢問前預處理。
然後對于每個詢問，我們先移動空白點到初始點，然後枚舉四個方向跑最短路即可
注意不需要移動的情況，否則可能比暴力分還低，洛谷的資料是65分
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N=32;
const int M=3610;
const int inf=0x3f3f3f3f;
int g[N][N],n,m,q,ex,ey,sx,sy,tx,ty;
int cal(int x,int y,int towards)
{
return ((x-1)*m+y)+(towards-1)*n*m;
}
const int dx[5]={0,-1,0,1,0};
const int dy[5]={0,0,1,0,-1};
int head[M],to[M<<3],Next[M<<3],edge[M<<3],cnt;
void add(int u,int v,int w)
{
to[++cnt]=v;Next[cnt]=head[u];edge[cnt]=w;head[u]=cnt;
}
struct node
{
int x,y,step;
node(int x,int y,int step)
{
this->x=x;this->y=y;this->step=step;
}
};
int used[N][N];
int Dis(int x0,int y0,int Tx,int Ty)
{
memset(used,0,sizeof(used));
queue <node > q;
node t0(x0,y0,0);
q.push(t0);
while(!q.empty())
{
int x=q.front().x,y=q.front().y,step=q.front().step;
q.pop();
if(used[x][y]) continue;
used[x][y]=1;
if(x==Tx&&y==Ty) return step;
for(int i=1;i<=4;i++)
{
int X=x+dx[i],Y=y+dy[i];
if(g[X][Y])
{
node tt(X,Y,step+1);
q.push(tt);
}
}
}
return inf;
}
void init()
{
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&g[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(!g[i][j]) continue;
g[i][j]=0;
for(int k=1;k<=4;k++)
{
int X=dx[k]+i,Y=dy[k]+j;
if(!g[X][Y]) continue;
int u=cal(i,j,k),f=k>2?-1:1;
int v0=cal(X,Y,k+f*2);
add(u,v0,1),add(v0,u,1);
for(int l=k+1;l<=4;l++)
{
int tX=dx[l]+i,tY=dy[l]+j;
if(!g[tX][tY]) continue;
int v=cal(i,j,l),w=Dis(X,Y,tX,tY);
add(u,v,w),add(v,u,w);
}
}
g[i][j]=1;
}
}
int dis[M],vis[M];
void spfa(int s)
{
memset(dis,0x3f,sizeof(dis));
queue <int > q;
q.push(s);
dis[s]=0;
while(!q.empty())
{
int u=q.front();
vis[u]=0;
q.pop();
for(int i=head[u];i;i=Next[i])
{
int v=to[i];
if(dis[v]>dis[u]+edge[i])
{
dis[v]=dis[u]+edge[i];
if(!vis[v]) vis[v]=1,q.push(v);
}
}
}
}
void work()
{
for(int i=1;i<=q;i++)
{
scanf("%d%d%d%d%d%d",&ex,&ey,&sx,&sy,&tx,&ty);
if(tx==sx&&ty==sy) {printf("0\n");continue;}
int ans=inf;
for(int j=1;j<=4;j++)
{
int X=sx+dx[j],Y=sy+dy[j];
if(!g[X][Y]) continue;
g[sx][sy]=0;
int cnt0=Dis(ex,ey,X,Y);
g[sx][sy]=1;
int u=cal(sx,sy,j);
spfa(u);
for(int k=1;k<=4;k++)
{
int tX=tx+dx[k],tY=ty+dy[k];
if(!g[tX][tY]) continue;
int v=cal(tx,ty,k);
ans=min(ans,dis[v]+cnt0);
}
}
if(ans==inf) printf("-1\n");
else printf("%d\n",ans);
}
}
int main()
{
init();
work();
return 0;
}