Problem:3290 新建题解

Solution_ID:29967            利用邻接矩阵的,SPFA,特高效

                   时间复杂度:Θ() 空间复杂度:Θ()

<h4>测试通过 Accepted</h4>
总耗时: 232 ms
20 / 20 数据通过测试.
运行结果
测试点#puzzle1.in  结果:<label>AC</label>    内存使用量:  232kB     时间使用量:  1ms     
测试点#puzzle10.in 结果:<label>AC</label> 内存使用量: 364kB 时间使用量: 0ms
测试点#puzzle11.in 结果:<label>AC</label> 内存使用量: 364kB 时间使用量: 4ms
测试点#puzzle12.in 结果:<label>AC</label> 内存使用量: 360kB 时间使用量: 12ms
测试点#puzzle13.in 结果:<label>AC</label> 内存使用量: 364kB 时间使用量: 9ms
测试点#puzzle14.in 结果:<label>AC</label> 内存使用量: 360kB 时间使用量: 20ms
测试点#puzzle15.in 结果:<label>AC</label> 内存使用量: 360kB 时间使用量: 36ms
测试点#puzzle16.in 结果:<label>AC</label> 内存使用量: 364kB 时间使用量: 36ms
测试点#puzzle17.in 结果:<label>AC</label> 内存使用量: 364kB 时间使用量: 8ms
测试点#puzzle18.in 结果:<label>AC</label> 内存使用量: 364kB 时间使用量: 20ms
测试点#puzzle19.in 结果:<label>AC</label> 内存使用量: 364kB 时间使用量: 36ms
测试点#puzzle2.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 1ms
测试点#puzzle20.in 结果:<label>AC</label> 内存使用量: 364kB 时间使用量: 36ms
测试点#puzzle3.in 结果:<label>AC</label> 内存使用量: 364kB 时间使用量: 1ms
测试点#puzzle4.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 0ms
测试点#puzzle5.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 0ms
测试点#puzzle6.in 结果:<label>AC</label> 内存使用量: 364kB 时间使用量: 0ms
测试点#puzzle7.in 结果:<label>AC</label> 内存使用量: 360kB 时间使用量: 0ms
测试点#puzzle8.in 结果:<label>AC</label> 内存使用量: 364kB 时间使用量: 4ms
测试点#puzzle9.in 结果:<label>AC</label> 内存使用量: 364kB 时间使用量: 8ms

我对这个效率挺满意的,毕竟写了好几天(捂脸....)其实是陪女朋友去了

程序可读性还可以,因为用了stl,加上本人对简洁的追求,不像某些博客写的程序没法看

还是因为用了stl的队列,时间超了200ms,如果手写队列,时间能够减半.

bfs1可以统计一下,如果搜到了4个状态,直接返回,剩下的都是无用搜索

bfs2做了很多无谓搜索,可以用A*优化一下,效果应该特别显著,由于本人比较懒,就先不优化了


bfs1计算对于每个位置的空格和棋子,棋子向各个方向移动的步数

由于不一定紧邻,bfs2计算棋子第一步移动所需步数


嗯,这道题的输入输出还可以优化一下,以上所有方法一起用的话,时间降到80问题不大,甚至更低,有志者可以试试(估计没有人了)

陪女朋友去了......

#include <bits/stdc++.h>
using namespace std;
int n, m, q;
int mp[33][33];
int xx[4] = {1, 0, 0, -1};
int yy[4] = {0, 1, -1, 0};
int dis[35][35];
int mm[35][35][4][4];
int dst[35][35][4];
const int INF = 0x3f3f3f3f;
int v[35][35][4];
struct p
{
    int x, y;
    p ( int _x, int _y ) : x ( _x ), y ( _y ) {}
};
inline int rev ( int dire )
{
    return dire ^ 3;
}
void showMat ( int p[35][35], int n, int m, const char *msg = "" )//debug用
{
    return;
    cout << msg << endl;
    for ( int i = 1; i <= n; ++i )
    {
        for ( int j = 1; j <= m; ++j )
            cout << ( p[i][j] < INF ? p[i][j] : 0 ) << " ";
        cout << "\n";
    }
    cout << flush;
}
void bfs ( int ex, int ey, int tx, int ty, int k ) // e空格 t目标
{
    memset ( dis, INF, sizeof dis );
    queue<p> qu;
    qu.push ( p ( ex, ey ) );
    dis[ex][ey] = 0;
    while ( !qu.empty() )
    {
        p pt = qu.front();
        qu.pop();
        for ( int kk = 0; kk < 4; ++kk )
        {
            int mx = pt.x + xx[kk], my = pt.y + yy[kk];
            if ( mp[mx][my] && ( mx != tx || my != ty ) && dis[mx][my] > dis[pt.x][pt.y] + 1 )
            {
                dis[mx][my] = dis[pt.x][pt.y] + 1;
                qu.push ( p ( mx, my ) );
            }
        }
    }
    char buf[16];
    sprintf ( buf, "(%d %d) (%d %d)", ex, ey, tx, ty );
    showMat ( dis, n, m, buf );
    for ( int kk = 0; kk < 4; ++kk )
    {
        int mx = tx + xx[kk], my = ty + yy[kk];
        mm[tx][ty][kk][k] = dis[mx][my] + 1;
//      printf ( "from %d %d to %d %d needs %d s bf sp at %d then sp at %d\n", tx, ty, mx, my, mm[tx][ty][kk][k], k, rev(kk) );
    }
}
void bfs2 ( int ex, int ey, int sx, int sy ) // e空格 t目标
{
    memset ( dis, INF, sizeof dis );
    queue<p> qu;
    qu.push ( p ( ex, ey ) );
    dis[ex][ey] = 0;
    while ( !qu.empty() )
    {
        p pt = qu.front();
        qu.pop();
        for ( int kk = 0; kk < 4; ++kk )
        {
            int mx = pt.x + xx[kk], my = pt.y + yy[kk];
            if ( mp[mx][my] && ( mx != sx || my != sy ) && dis[mx][my] > dis[pt.x][pt.y] + 1 )
            {
                dis[mx][my] = dis[pt.x][pt.y] + 1;
                qu.push ( p ( mx, my ) );
            }
        }
    }
    char buf[16];
    sprintf ( buf, "(%d %d) (%d %d)", ex, ey, sx, sy );
    showMat ( dis, n, m, buf );
    for ( int kk = 0; kk < 4; ++kk )
    {
        int mx = sx + xx[kk], my = sy + yy[kk];
        if(mp[mx][my])
            dst[mx][my][rev(kk)] = dis[mx][my] + 1;
    }
}
int main()
{
    cin >> n >> m >> q;
    for ( int i = 1; i <= n; ++i )
    {
        for ( int j = 1; j <= m; ++j )
        {
            cin >> mp[i][j];
        }
    }
    for ( int i = 1; i <= n; ++i )
    {
        for ( int j = 1; j <= m; ++j )
        {
            if ( !mp[i][j] )
            {
                continue;
            }
            for ( int k = 0; k < 4; ++k )
            {
                int mx = i + xx[k], my = j + yy[k];
                if ( mp[mx][my] )
                {
                    bfs ( mx, my, i, j, k );
                }
            }
        }
    }
    while ( q-- )
    {
        memset ( dst, INF, sizeof dst );
        int ex, ey, sx, sy, tx, ty;
        cin >> ex >> ey >> sx >> sy >> tx >> ty;
        if (sx==tx && sy==ty)//这里不写大概只能得70分,好坑
        {
            cout << 0 << endl;
            continue;
        }
        bfs2 ( ex, ey, sx, sy );
        queue<pair<p, int> > qu;
        for ( int kk = 0; kk < 4; ++kk )
        {
            int mx = sx + xx[kk], my = sy + yy[kk];
            if(mp[mx][my])
                qu.push ( make_pair ( p ( mx, my ), rev(kk) ) );
            v[mx][my][rev(kk)] = 1;
        }
        while ( !qu.empty() )
        {
            p pt = qu.front().first;
            int dire = qu.front().second;
            qu.pop();
            v[pt.x][pt.y][dire] = 0;
            for ( int k = 0; k < 4; ++k )
            {
                int mx = pt.x + xx[k], my = pt.y + yy[k];
                if ( mp[mx][my] && dst[mx][my][rev(k)] > dst[pt.x][pt.y][dire] + mm[pt.x][pt.y][dire][k] )
                {
                    dst[mx][my][rev(k)] = dst[pt.x][pt.y][dire] + mm[pt.x][pt.y][dire][k];
                    if ( !v[mx][my][rev(k)] )
                        qu.push ( make_pair ( p ( mx, my ), rev(k) ) );
                    v[mx][my][rev(k)] = 1;
                }
            }
        }
        int ans = INF;
        for ( int k = 0; k < 4; ++k )
        {
            ans = min(dst[tx][ty][k], ans);
        }
        cout << (ans < INF ? ans : -1)<< endl;
    }
    return 0;
}




by 29731 十一月 3, 2017, 8:35 a.m.

Solution_ID:29689            A* 启发式搜索

                   时间复杂度:Θ() 空间复杂度:Θ()

详见:http://k-xzy.cf/archives/2849


#include <bits/stdc++.h>
using namespace std;
template<typename _Tp>inline void IN(_Tp&dig)
{
	char c;dig=0;
	while(c=getchar(),!isdigit(c));
	while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
int n,m,q,mp[35][35],ex,ey,sx,sy,tx,ty,tmp[35][35],dis[35][35][35][35][4],htab[10][35][35];
bool vis[35][35];
struct P{int h,w;}dirc[4]={{-1,0},{1,0},{0,-1},{0,1}};
struct ST
{
	int h,w,d,G,H;
	bool operator < (const ST another)const{return G+H>another.G+another.H;}
};
queue<P> que;
priority_queue<ST> pq;
inline int H(int h,int w){return abs(h-tx)+abs(w-ty);}
inline void bfs(int x1,int y1,int x2,int y2)
{
	memset(tmp,0,sizeof(tmp)),memset(vis,0,sizeof(vis));
	que.push((P){x1,y1}),vis[x1][y1]=1;
	for(int i=0;i<4;i++)dis[x1][y1][x2][y2][i]=-1;
	while(!que.empty())
	{
		P F=que.front(),nxt;que.pop();
		for(int i=0;i<4;i++)
		{
			if(F.h-dirc[i].h==x2&&F.w-dirc[i].w==y2)dis[x1][y1][x2][y2][i]=tmp[F.h][F.w];
			nxt.h=F.h+dirc[i].h,nxt.w=F.w+dirc[i].w;
			if(nxt.h<1||nxt.h>n||nxt.w<1||nxt.w>m)continue;
			if(vis[nxt.h][nxt.w]||!mp[nxt.h][nxt.w]||(nxt.h==x2&&nxt.w==y2))continue;
			tmp[nxt.h][nxt.w]=tmp[F.h][F.w]+1;
			que.push(nxt),vis[nxt.h][nxt.w]=1;
		}
	}
}
int main()
{
	IN(n),IN(m),IN(q);
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)IN(mp[i][j]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)if(mp[i][j])
			for(int k=0;k<4;k++)if(mp[i+dirc[k].h][j+dirc[k].w])
					bfs(i+dirc[k].h,j+dirc[k].w,i,j);
	while(q--)
	{
		memset(htab,127,sizeof(htab));
		while(!pq.empty())pq.pop();
		IN(ex),IN(ey),IN(sx),IN(sy),IN(tx),IN(ty),bfs(ex,ey,sx,sy);
		if(sx==tx&&sy==ty){printf("0\n");goto end;}
		for(int i=0;i<4;i++)
			if(dis[ex][ey][sx][sy][i]!=-1)
			{
				ST nxt=(ST){sx,sy,i,dis[ex][ey][sx][sy][i],H(sx,sy)};
				pq.push(nxt),htab[nxt.d][nxt.h][nxt.w]=dis[ex][ey][sx][sy][i];
			}
		while(!pq.empty())
		{
			ST F=pq.top();pq.pop();
			if(F.h==tx&&F.w==ty){printf("%d\n",F.G);goto end;}
			int eh=F.h+dirc[F.d].h,ew=F.w+dirc[F.d].w;
			for(int i=0;i<4;i++)
				if(dis[eh][ew][F.h][F.w][i]!=-1)
				{
					ST nxt=(ST){F.h,F.w,i,F.G+dis[eh][ew][F.h][F.w][i],F.H};
					if(htab[nxt.d][nxt.h][nxt.w]>F.G+dis[eh][ew][F.h][F.w][i])
						pq.push(nxt),htab[nxt.d][nxt.h][nxt.w]=F.G+dis[eh][ew][F.h][F.w][i];
				}
			ST nxt=(ST){eh,ew,F.d^1,F.G+1,H(eh,ew)};
			if(htab[nxt.d][nxt.h][nxt.w]>F.G+1)
				pq.push(nxt),htab[nxt.d][nxt.h][nxt.w]=F.G+1;
		}
		printf("-1\n");
		end:continue;
	}
	return 0;
}

by 35608 十月 19, 2017, 5:22 p.m.

Solution_ID:21476            和楼下的一样 bfs+spfa

                   时间复杂度:Θ(O(n^4+q*n^2)) 空间复杂度:Θ(O(n*m*8))

也许你也不知道怎么写:

http://herrwerner.lofter.com/post/1dacb250_c635fbf


by 17736 九月 19, 2016, 8:40 p.m.

Solution_ID:20475            啊哈

                   时间复杂度:Θ() 空间复杂度:Θ()

详细题解自己看博客啦啦啦

反正我是看了题解的啦啦啦

然而初始化很重要啊啦啦啦

啦啦啦之歌最有趣了啦啦啦

#include<cstdio>

#include<cstring>

const int N=31,d[4][2]={{1,0},{0,1},{-1,0},{0,-1}},inf=1010580540;

struct xint{int x,y;}q[N*N];

struct yint{int x,y,dir;}qq[N*N*4];

int n,m,T,h,t,ex,ey,sx,sy,tx,ty;

int a[N][N],dis[N][N],di[N][N][4][4],dist[N][N][4];

bool b[N][N][4];

bool ok(int x,int y){return x>0&&x<=n&&y>0&&y<=m&&a[x][y];}

void yuchuli(int sx,int sy)//预处理每个点四个方向上空格到另外方向的移动次数(不经过这个点) 

{

    for (int tql=0;tql<4;tql++)//tql=太强啦 

    {

        int nzql=sx+d[tql][0],wzrl=sy+d[tql][1];//nzql=您最强啦 wzrl=我最弱了 

        if (ok(nzql,wzrl))

        {

            h=t=1;

            q[1]=(xint){nzql,wzrl};

            memset(dis,inf,sizeof dis);

            dis[nzql][wzrl]=0;

            while (h<=t)

            {

                int x=q[h].x,y=q[h].y;

                h++;

                for (int i=0;i<4;i++)

                {

                    int xx=x+d[i][0],yy=y+d[i][1];

                    if (ok(xx,yy)&&(xx!=sx||yy!=sy)&&dis[xx][yy]==inf)

                        q[++t]=(xint){xx,yy},dis[xx][yy]=dis[x][y]+1;

                }

            }

            for (int i=0;i<4;i++)

                if (i!=tql)

                {

                    int x=sx+d[i][0],y=sy+d[i][1];

                    if (ok(x,y)&&dis[x][y]!=inf)

                        di[sx][sy][tql][i]=dis[x][y];

                }

            /*if (sx==2&&sy==2&&tql==1)

            for (int i=1;i<=n;i++)

            {

                for (int j=1;j<=m;j++)

                    printf("%d ",dis[i][j]);

                printf("\n");

            }*/

        }

    }

    //if (sx==2&&sy==2)

    // printf("%d\n",di[sx][sy][1][0]);

}

void yuchuli2()//预处理一开始空格到棋子初始位置四周的移动次数(不经过棋子) 

{

    h=t=1;

    q[1]=(xint){ex,ey};

    memset(dis,inf,sizeof dis);

    dis[ex][ey]=0;

    while (h<=t)

    {

        int x=q[h].x,y=q[h].y;

        h++;

        for (int i=0;i<4;i++)

        {

            int xx=x+d[i][0],yy=y+d[i][1];

            if (ok(xx,yy)&&(xx!=sx||yy!=sy)&&dis[xx][yy]==inf)

                q[++t]=(xint){xx,yy},dis[xx][yy]=dis[x][y]+1;

        }

    }

}

void solve()//spfa 

{

    scanf("%d%d%d%d%d%d",&ex,&ey,&sx,&sy,&tx,&ty);

    if (sx==tx&&sy==ty) {printf("0\n"); return;}

    yuchuli2();

    memset(dist,inf,sizeof dist);

    memset(b,0,sizeof b);

    h=1; t=0;

    for (int i=0;i<4;i++)

    {

        int x=sx+d[i][0],y=sy+d[i][1];

        if (ok(x,y)&&dis[x][y]!=inf)

            qq[++t]=(yint){sx,sy,i},dist[sx][sy][i]=dis[x][y],b[sx][sy][i]=1;

    }

    while (h<=t)

    {

        int x=qq[h].x,y=qq[h].y,dir=qq[h].dir;

        h++;

        b[x][y][dir]=0;

        //棋子与空格交换 

        int xx=x+d[dir][0],yy=y+d[dir][1],dire=(dir+2)%4;

        if (dist[xx][yy][dire]>dist[x][y][dir]+1)

        {

            dist[xx][yy][dire]=dist[x][y][dir]+1;

            if (!b[xx][yy][dire])

            {

                qq[++t]=(yint){xx,yy,dire},b[xx][yy][dire]=1;

                //if (xx==2&&yy==2&&dire==0) printf("%d %d %d\n",x,y,dir);

            }

        }

        //空格移动到另一方向上 

        for (int i=0;i<4;i++)

            if (i!=dir&&ok(x+d[i][0],y+d[i][1])&&di[x][y][dir][i]!=inf&&dist[x][y][i]>dist[x][y][dir]+di[x][y][dir][i])

            {

                dist[x][y][i]=dist[x][y][dir]+di[x][y][dir][i];

                if (!b[x][y][i])

                {

                    qq[++t]=(yint){x,y,i},b[x][y][i]=1;

                    //if (x==2&&y==2&&i==0) printf("%d %d %d\n",x,y,dir);

            }

        }

    }

    //for (int i=1;i<=t;i++)

    // printf("%d %d %d\n",qq[i].x,qq[i].y,qq[i].dir);

    int ans=inf;

    for (int i=0;i<4;i++)

        if (dist[tx][ty][i]<ans)

            ans=dist[tx][ty][i];

    if (ans==inf) printf("-1\n");

    else printf("%d\n",ans);

}

int main()

{

    memset(di,inf,sizeof di);

    scanf("%d%d%d",&n,&m,&T);

    for (int i=1;i<=n;i++)

        for (int j=1;j<=m;j++)

            scanf("%d",&a[i][j]);

    for (int i=1;i<=n;i++)

        for (int j=1;j<=m;j++)

            if (a[i][j])

                yuchuli(i,j);

    while (T--) solve();

    return 0;

}


by 22234 八月 8, 2016, 12:40 p.m.

Solution_ID:20163            神TM 80分做法

                   时间复杂度:Θ() 空间复杂度:Θ()

读入优化卡常加几个小剪枝

神TM 80分噗.

/*
作者:M3
题目:p3290 华容道
*/

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 30 + 5;
const int MAXS = 810000 + 10;
const int dx[5] = {0, 0, 0, 1, -1};
const int dy[5] = {0, 1, -1, 0, 0};

inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}

struct data { int x, y, kx, ky, depth; }que[MAXS];

int n, m, q;
int map[MAXN][MAXN];
bool vis[MAXN][MAXN][MAXN][MAXN];

inline bool check(int x, int y, int kx, int ky) {
    if(x < 1 || y < 1 || x >n || y > m || !map[x][y] || !map[kx][ky] || vis[x][y][kx][ky]) return false;
    vis[x][y][kx][ky] = true;
    return true;
}

inline void bfs() {
    memset(vis, false, sizeof(vis));
    int head = 0, tail = 0;
    int ex, ey;
    que[0].kx = read(), que[0].ky = read();
    que[0].x = read(), que[0].y = read();
    ex = read(), ey = read();
    if(ex == que[0].x && ey == que[0].y) { printf("0\n"); return; }
    vis[que[0].x][que[0].y][que[0].kx][que[0].ky] = true;
    while(head <= tail) {
        for(int i = 1, x, y, kx, ky; i <= 4; ++i) {
            x = que[head].x, y = que[head].y;
            kx = que[head].kx + dx[i], ky = que[head].ky +dy[i];
            if(x == kx && y == ky) { x = que[head].kx, y = que[head].ky; }
            if(check(x, y, kx, ky)) {
                tail++;
                que[tail].x = x, que[tail].y = y;
                que[tail].kx = kx, que[tail].ky = ky;
                que[tail].depth = que[head].depth + 1;
                if(x == ex && y == ey) {
                    printf("%d\n", que[tail].depth);
                    return;
                }
            }
        }
        head++;
    }
    printf("-1\n");
    return;
}

int main() {
    n = read(), m = read(), q = read();
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            map[i][j] = read();
    for(int i = 1; i <= q; ++i) bfs();
    return 0;
}


其实是不会标解...


by 29428 七月 30, 2016, 12:06 p.m.

Solution_ID:11952            广搜+SPFA

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<stdio.h>

#include<queue>

#include<vector>

#include<string.h>

#include<iostream>

using namespace std;


typedef pair<int,int> pii;

queue<pii>Q;


const int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};

int way[40][40][10],cnt[10],dist[40][40],val[10010];

int woc[4]= {1,0,3,2};

int V,S,T,sx1,sy1,sx2,sy2,sx3,sy3,st[10000];

int map[40][40];


struct sugar

{

int u,v,next;

}a[100010];


int m,n,q,tot;


void add(int i,int j,int k)

{

a[++tot].u = k;

a[tot].v = j;

a[tot].next = st[i];

st[i] = tot;

}


int bfs(int sx1,int sy1,int sx2,int sy2){

if(sx1 == sx2 && sy1 == sy2) return 0;

while(!Q.empty()) Q.pop();//检查 

    memset(dist,0x3f,sizeof(dist));

    dist[sx1][sy1] = 0;

    Q.push(make_pair(sx1,sy1));

    while(!Q.empty())

    {

    pii u = Q.front();

    Q.pop();

    for(int k = 0 ; k <= 3 ; k++)

    {

    if(dist[u.first + dir[k][0]][u.second + dir[k][1]] && dist[u.first + dir[k][0]][u.second+dir[k][1]]==dist[39][39] && map[u.first+dir[k][0]][u.second+dir[k][1]])

    {

   dist[u.first + dir[k][0]][u.second + dir[k][1]] = dist[u.first][u.second] + 1;

    if(u.first + dir[k][0] == sx2 && u.second + dir[k][1] == sy2) return dist[u.first][u.second] + 1;

    Q.push(make_pair(u.first + dir[k][0],u.second + dir[k][1]));

    }

    }

    }

    return dist[39][39];

}


void check(){

for(int i = 1 ; i <= n ; i++)

   for(int j = 1 ; j <= m ; j++)

       for(int k = 0 ; k <= 3 ; k++)

           if(map[i + dir[k][0]][j + dir[k][1]] && map[i][j])

            add(way[i][j][k],way[i+dir[k][0]][j+dir[k][1]][woc[k]],1);

}    

int spfa(int S,int T)

{

    int que[10010],p[10010],f=1,l=1;

memset(p,0,sizeof(p));

    memset(que,0,sizeof(que));

    memset(val,0x3f,sizeof(val));//111111 63

val[S] = 0;que[1] = S;p[S] = 1;

while(f <= l)

{

int j = que[f++];

p[j] = 0;

for(int i = st[j] ; i != 0 ; i = a[i].next)

{

  if(a[i].u + val[j] < val[a[i].v])

  {

       val[a[i].v] = a[i].u + val[j];

       if(!p[a[i].v]) que[++l] = a[i].v,p[a[i].v] = 1;

  }

   }

}

return val[T];

}


void output()

{

for(int i = 1 ; i <= q ; i++)

{

  scanf("%d%d%d%d%d%d",&sx1,&sy1,&sx2,&sy2,&sx3,&sy3);

  if(map[sx2][sy2] == 0 || map[sx3][sy3] == 0 ){printf("-1\n");continue;}

  if(sx2 == sx3 && sy2 == sy3) {printf("0\n");continue;}

  map[sx2][sy2] = 0;

  for(int j = 0 ; j <= 3 ; j++)

   if(map[sx2+dir[j][0]][sy2+dir[j][1]])

      cnt[j] = bfs(sx1,sy1,sx2+dir[j][0],sy2+dir[j][1]);

   map[sx2][sy2] = 1;

   T = ++V;

  for(int j = 0 ; j <= 3 ; j++)

      if(map[sx3 + dir[j][0]][sy3 + dir[j][1]] == 1)

         add(way[sx3][sy3][j],T,0);

  S = ++V;

  for(int j = 0 ; j <= 3 ; j++)

  if(map[sx2 + dir[j][0]][sy2 + dir[j][1]])

add(S,way[sx2][sy2][j],cnt[j]);

int ans = spfa(S,T);

if(ans >= 1061109567) printf("-1\n");

else printf("%d\n",ans);

}

}

   

   


int main()

{

freopen("puzzle.in","r",stdin);

freopen("puzzle.out","w",stdout);

scanf("%d%d%d",&n,&m,&q);

for(int i = 1 ; i <= n ; i++)

   for(int j = 1 ; j <= m ; j++)

       scanf("%d",map[i]+j);

for(int i = 1 ; i <= n ; i++)

   for(int j = 1 ; j <= m ; j++)

    for(int k = 0 ; k <= 3 ; k++)

       way[i][j][k] = ++V;// 方向

for(int i = 1 ; i <= n ; i++)

   for(int j = 1 ; j <= m ; j++)

{

 if(map[i][j])

 {

   map[i][j] = 0;

for(int k = 0 ; k <= 3 ; k++)

{

  if(map[i+dir[k][0]][j+dir[k][1]])

  {

      for(int o = 0 ; o <= 3 ; o++)

  {

      if(o != k && map[i+dir[o][0]][j+dir[o][1]])

  add(way[i][j][k],way[i][j][o],bfs(i+dir[k][0],j+dir[k][1],i+dir[o][0],j+dir[o][1]));

  }

  }

   }

   map[i][j] = 1;

 }

   }

check();

output();

return 0;

}


by 20118 九月 25, 2015, 12:19 p.m.

Solution_ID:11196            宽搜+最短路径

                   时间复杂度:Θ() 空间复杂度:Θ()

type arr=record

     x,y,pre:integer;

     end;

     arr1=record

     x,y,d:integer;

     end;

     arr2=record

     st,en,w:integer;

     end;

     arr3=record

     x,y:longint;

     end;

const dx:array[1..4]of integer=(-1,0,1,0);

      dy:array[1..4]of integer=(0,1,0,-1);

var map:array[0..35,0..35]of integer;

    b:array[1..10000]of arr;

    hash:array[1..30,1..30]of boolean;

    ha:array[1..30,1..30]of boolean;

    a:array[0..35,0..35,1..4,1..4]of integer;

    num:array[0..35,0..35,0..4]of integer;

    edge:array[0..100000]of arr2;

    mark:array[0..10000]of arr3;

    dis:array[1..10000]of longint;

    haha:array[1..10000]of boolean;

    que:array[1..100005]of longint;

    n,m,q,i,j,k,l,x1,x2,y1,y2,x3,y3,xb,yb,ans,tot,tott,u,v,d,x,y,sta,f,r,min,minn:longint;

    t:arr;

    st:arr1;


procedure qs(l,r:longint);

  var x,y:longint;

      mid,t:arr2;

  begin

  x:=l;y:=r;mid:=edge[(l+r)div 2];

  repeat

    while(edge[x].st<mid.st)or(edge[x].st=mid.st)and(edge[x].en<mid.en)do inc(x);

    while(edge[y].st>mid.st)or(edge[y].st=mid.st)and(edge[y].en>mid.en)do dec(y);

    if x<=y then begin

      t:=edge[x];edge[x]:=edge[y];edge[y]:=t;

      inc(x);dec(y);

      end;

    until x>y;

    if l<y then qs(l,y);

    if x<r then qs(x,r);

    end;


procedure bfs1(x1,y1,x2,y2,i,j,k,l:integer);

  var f,r,s,p,q:integer;

  begin

  fillchar(hash,sizeof(hash),true);

  f:=0;r:=1;b[1].x:=x1;b[1].y:=y1;b[1].pre:=0;hash[x1,y1]:=false;

  while f<r do begin

    inc(f);

    t:=b[f];

    for s:=1 to 4 do begin

      p:=t.x+dx[s];q:=t.y+dy[s];

      if(map[p,q]=1)and hash[p,q] then begin

        inc(r);b[r].x:=p;b[r].y:=q;b[r].pre:=t.pre+1;

        hash[p,q]:=false;

        if(p=x2)and(q=y2)then begin

          a[i,j,k,l]:=b[r].pre+1;

          exit;

          end;

        end;

      end;

    end;

  end;


{function judge(p,q,x1,y1:integer;var st:arr1):boolean;

  var i,x,y:integer;

  begin

  judge:=false;

  for i:=1 to 4 do begin

    x:=p+dx[i];y:=q+dy[i];

    if(x=x1)and(y=y1)then begin

      st.x:=x1;st.y:=y1;

      case i of

        1:st.d:=3;

        2:st.d:=4;

        3:st.d:=1;

        4:st.d:=2;

        end;

      exit(true);

      end;

    end;

  end;}


procedure bfs2(xb,yb,x3,y3:integer);

  var f,r,s,p,q:integer;

  begin

  fillchar(ha,sizeof(ha),true);

  f:=0;r:=1;b[1].x:=xb;b[1].y:=yb;b[1].pre:=0;ha[xb,yb]:=false;ha[x1,y1]:=false;

  while f<r do begin

    inc(f);

    t:=b[f];

    for s:=1 to 4 do begin

      p:=t.x+dx[s];q:=t.y+dy[s];

      if(map[p,q]=1)and(ha[p,q])then begin

        inc(r);b[r].x:=p;b[r].y:=q;b[r].pre:=t.pre+1;

        ha[p,q]:=false;

        if(p=x3)and(q=y3)then begin

          ans:=b[r].pre;

          exit;

          end;

        end;

      end;

    end;

  ans:=-1;

  end;


begin

assign(input,'puzzle.in');reset(input);

assign(output,'puzzle.out');rewrite(output);

readln(n,m,q);

for i:=0 to n+1 do

  for j:=0 to m+1 do

    map[i,j]:=0;

for i:=1 to n do

  for j:=1 to m do begin

    read(map[i,j]);

    end;

for i:=1 to n do

  for j:=1 to m do

    for k:=1 to 4 do

      for l:=1 to 4 do

        a[i,j,k,l]:=maxint;//初始化

for i:=1 to n do

  for j:=1 to m do

    if map[i,j]=1 then begin

      map[i,j]:=0;//宽搜时空格不可经过当前节点

      for k:=1 to 4 do

        for l:=1 to 4 do begin

          x1:=i+dx[k];y1:=j+dy[k];

          x2:=i+dx[l];y2:=j+dy[l];

          if k<>l then begin

            if(map[x1,y1]=1)and(map[x2,y2]=1)then bfs1(x1,y1,x2,y2,i,j,k,l);//宽搜求出空格从当前节点的一个方向挪到另一个方向所需要的步数

            end

          else

            if map[x1,y1]=1 then a[i,j,k,l]:=1;

          end;

      map[i,j]:=1;

      end;

{for i:=1 to n do

  for j:=1 to m do begin

    writeln('(',i,',',j,'):');

    for k:=1 to 4 do begin

      for l:=1 to 6 do write(' ');

      for l:=1 to 4 do

        write(a[i,j,k,l],' ');

      writeln;

      end;

    end;  }


tott:=0;

for i:=1 to n do

  for j:=1 to m do

    for k:=1 to 4 do begin

      inc(tott);

      num[i,j,k]:=tott;

      end;//给每个状态编号

tot:=0;

for i:=1 to n do

  for j:=1 to m do

    for k:=1 to 4 do

      for l:=1 to 4 do

        if a[i,j,k,l]<maxint then begin

          u:=i+dx[l];v:=j+dy[l];

          case l of

            1:d:=3;

            2:d:=4;

            3:d:=1;

            4:d:=2;

            end;

          x:=num[i,j,k];y:=num[u,v,d];

          inc(tot);

          edge[tot].st:=x;edge[tot].en:=y;edge[tot].w:=a[i,j,k,l];

          end;//把每个状态抽象为一个点,相邻状态间转移所需要的步数即为边,之后就是跑最短路径了

qs(1,tot);

//for i:=1 to tot do writeln(edge[i].st,' ',edge[i].en,' ',edge[i].w);

edge[tot+1].st:=edge[tot].st+1;

for i:=1 to tot+1 do

  if edge[i].st>edge[i-1].st then begin

    mark[edge[i].st].x:=i;

    mark[edge[i-1].st].y:=i-1;

    end;//spfa初始化


for l:=1 to q do begin

  readln(xb,yb,x1,y1,x2,y2);

  if(x1=x2)and(y1=y2)then begin writeln(0);continue;end;//特殊情况,初始节点就是目标节点,坑啊

  minn:=maxlongint;

  for k:=1 to 4 do begin

    x3:=x1+dx[k];y3:=y1+dy[k];

    st.x:=x1;st.y:=y1;st.d:=k;

    ans:=0;

    if(xb=x3)and(yb=y3)then ans:=0

    else

      bfs2(xb,yb,x3,y3);//宽搜从空格的初始位置移到要移动的棋子旁边需要的步数,空格在四个方向都要跑一遍spfa

    if ans=-1 then continue

    else begin

      sta:=num[st.x,st.y,st.d];//起点

      for i:=1 to tott do dis[i]:=maxlongint;

      dis[sta]:=0;

      fillchar(haha,sizeof(haha),false);

      f:=0;r:=1;que[1]:=sta;haha[sta]:=true;

      repeat

        f:=f mod 100000;

        inc(f);

        haha[que[f]]:=false;

        for i:=mark[que[f]].x to mark[que[f]].y do

          if dis[edge[i].en]>dis[que[f]]+edge[i].w then begin

            dis[edge[i].en]:=dis[que[f]]+edge[i].w;

            if not haha[edge[i].en] then begin

              r:=r mod 100000;

              inc(r);

              que[r]:=edge[i].en;

              haha[edge[i].en]:=true;

              end;

            end;

      until f=r;

      min:=maxlongint;

      for i:=1 to 4 do

        if dis[num[x2,y2,i]]<min then min:=dis[num[x2,y2,i]];

      if min<maxlongint then

        if min+ans<minn then minn:=min+ans;

      end;//裸spfa,不解释

    end;

  if minn<maxlongint then writeln(minn) else writeln(-1);

  end;


  close(input);close(output);

end.





by 24037 八月 27, 2015, 9:11 p.m.

Solution_ID:5527            广搜+最短路

                   时间复杂度:Θ(m^2 * n^2) 空间复杂度:Θ(m^2 * n^2)

预处理部分:

因为对棋子的移动最终对应着对空格的移动,而空格的初始位置(非起始情况)一定是在目标棋子的上下左右的。

这样我们把空格先准备好,然后移动一下棋子,这种操作的代价很容易发现是常数。因此可以使用最短路。方法是把每个棋子一分为四,上下左右,[一个棋子的左边]就代表了空格的初始位置在这个棋子的左边,即它前一次是从左边移过来的。每个棋子的每一边可以建立于上面棋子的下边,下面棋子的上边等的联系(用一个有向图来存储),并存储价值。

最后还有一个小问题,就是每次的q的空白位置不是在目标棋子的上下左右。这时候选择目标棋子的一类,并且修改其与周遭棋子联系的边权,然后做最短路,然后记得要改回去。

最短路用dijk也可以ac.


by 3303 五月 2, 2014, 1:11 a.m.

Solution_ID:4222            未知

                   时间复杂度:未知 空间复杂度:未知

#include <iostream> #include <algorithm> #include <cstring> #include <queue> using namespace std; #define MAXN 32 #define MAXV 50010 #define inf (1<<26) const int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; struct edge { edge *next; int t,d; edge () { next=NULL; } } *head[MAXV]; void AddEdge(int s,int t,int d) { edge *p=new(edge); p->t=t,p->d=d; p->next=head[s]; head[s]=p; } int Map[MAXN][MAXN],n,m,q,ex,ey,sx,sy,tx,ty; int v[MAXN][MAXN][4],V=0; int dist[MAXN][MAXN],Move[MAXN][MAXN][4][4]; int Dist[MAXV]; bool f[MAXV]; int S,T; struct node { int x,y; node (int _x,int _y):x(_x),y(_y) { } }; queue<node>Q; int Bfs(int Sx,int Sy,int Tx,int Ty) { if (Sx==Tx&&Sy==Ty) return 0; while (!Q.empty()) Q.pop(); for (int i=0;i++<n;) { for (int j=0;j++<m;) { dist[i][j]=inf; } } dist[Sx][Sy]=0; Q.push(node(Sx,Sy)); while (!Q.empty()) { node u=Q.front(); Q.pop(); for (int i=0;i<4;i++) { if (Map[u.x+dir[i][0]][u.y+dir[i][1]]&&dist[u.x+dir[i][0]][u.y+dir[i][1]]==inf) { dist[u.x+dir[i][0]][u.y+dir[i][1]]=dist[u.x][u.y]+1; if (u.x+dir[i][0]==Tx&&u.y+dir[i][1]==Ty) return dist[u.x][u.y]+1; Q.push(node(u.x+dir[i][0],u.y+dir[i][1])); } } } return inf; } queue<int>Pq; int spfa() { for (int i=0;i++<V;) Dist[i]=inf; memset(f,true,sizeof(f)); while (!Pq.empty()) Pq.pop(); Dist[S]=0; Pq.push(S); while (!Pq.empty()) { int u=Pq.front(); Pq.pop(); if (!f[u]) continue; f[u]=false; for (edge *p=head[u];p;p=p->next) { if (Dist[p->t]>Dist[u]+p->d) { Dist[p->t]=Dist[u]+p->d; f[p->t]=true; Pq.push(p->t); } } } return Dist[T]<inf?Dist[T]:-1; } int main() { cin>>n>>m>>q; memset(Map,0,sizeof(Map)); for (int i=0;i++<n;) { for (int j=0;j++<m;) { cin>>Map[i][j]; for (int k=0;k<4;k++) { v[i][j][k]=++V; } } } for (int i=0;i++<n;) { for (int j=0;j++<m;) { for (int k=0;k<4;k++) { for (int h=0;h<4;h++) { Move[i][j][k][h]=inf; } } } } for (int i=0;i++<n;) { for (int j=0;j++<m;) { if (Map[i][j]) { Map[i][j]=0; for (int k=0;k<4;k++) { if (Map[i+dir[k][0]][j+dir[k][1]]) { for (int h=0;h<4;h++) { if (Map[i+dir[h][0]][j+dir[h][1]]) { Move[i][j][k][h]=Bfs(i+dir[k][0],j+dir[k][1],i+dir[h][0],j+dir[h][1])+1; } } } } Map[i][j]=1; } } } memset(head,0,sizeof(head)); for (int i=0;i++<n;) { for (int j=0;j++<m;) { for (int k=0;k<4;k++) { for (int h=0;h<4;h++) { if (Move[i][j][k][h]<inf) { AddEdge(v[i][j][k],v[i+dir[h][0]][j+dir[h][1]][h^1],Move[i][j][k][h]); } } } } } while (q--) { cin>>ex>>ey>>sx>>sy>>tx>>ty; if (sx==tx&&sy==ty) { cout<<0<<endl; continue; } S=++V; T=++V; if (Map[sx][sy]==0||Map[tx][ty]==0) { cout<<-1<<endl; continue; } Map[sx][sy]=0; for (int i=0;i<4;i++) { if (Map[sx+dir[i][0]][sy+dir[i][1]]) { int D=Bfs(ex,ey,sx+dir[i][0],sy+dir[i][1]); if (D<inf) { AddEdge(S,v[sx][sy][i],D); } } } Map[sx][sy]=1; for (int i=0;i<4;i++) { if (Map[tx+dir[i][0]][ty+dir[i][1]]) { AddEdge(v[tx][ty][i],T,0); } } cout<<spfa()<<endl; } return 0; }

有点乱,可是毕竟有程序,麻烦点个小手,谢谢啦。


by 9238 一月 23, 2014, 7:03 p.m.

Solution_ID:3616            SPFA

                   时间复杂度:未知 空间复杂度:未知

将每种状态转化为一个节点,人为添加起点与终点,进行SPFA;

代码见博客<a href="http://blog.sina.com.cn/u/3792057180">http://blog.sina.com.cn/u/3792057180</a>


by 6147 十二月 1, 2013, 8:40 a.m.

Solution_ID:3474            最短路

                   时间复杂度:O(n^4+qn^2 log n) 空间复杂度:O(n^2)

先O(n^4)预处理,然后跑q次最短路。

详细题解:

Day1:<a href="http://wenku.baidu.com/view/a3aa6a0c5901020207409c92.html">http://wenku.baidu.com/view/a3aa6a0c5901020207409c92.html</a>

Day2:<a href="http://wenku.baidu.com/view/86b0a347a98271fe910ef9ef.html">http://wenku.baidu.com/view/86b0a347a98271fe910ef9ef.html</a>

(这里的非官方数据存在两种不合法情况:1.空白格跟要移动的棋子在同一位置 2.空白格位置在输入中是0,这两种情况均为无解,题解中代码未加判断,请自行补充)


by 4669 十一月 15, 2013, 9:05 p.m.