Demo entry 6762977

hard

   

Submitted by 反对法 on Oct 18, 2018 at 09:48
Language: C++. Code size: 1.9 kB.

/*
*** #23 找礼物
*** 记忆化DFS
*/
#include <bits/stdc++.h>
#define llt long long 
using namespace std;

const int N=4;
const int n=4,m=4;

char s[N][N];

int finish=0;
int offset[][2]={
	0,1,
	0,-1,
	1,0,
	-1,0
};
int vis[N][N][N][N][(1<<16)+1]={0};
	//num[i][j][u][v][status] 记录磊哥走到(i,j)、
    //小凡走到(u,v),status的二进制数位为1的点表示已经搜索过了的时间数

struct node{
	int x[2],y[2];//记录两人的坐标
	int status;// 走过点的状态数
}curNode;


bool is_ok(int a,int b){// 监测是否越界
	return 0<=a&&a<n&&0<=b&&b<m;
}
int bfs(int sx,int sy){//'S'的坐标
	vis[sx][sy][sx][sy][1<<(sx*m+sy)]=1;//从1开始,答案减1.
	node tmp;
	tmp.x[0]=tmp.x[1]=sx;
	tmp.y[0]=tmp.y[1]=sy;
	tmp.status=1<<(sx*m+sy);

	queue <node> q;
	q.push(tmp);
	while(!q.empty()){
		curNode=q.front();
		q.pop();
		if(curNode.status==finish)
			return vis[curNode.x[0]][curNode.y[0]][curNode.x[1]][curNode.y[1]][curNode.status]-1;
		for(int i=0;i<4;++i){
			tmp.x[0]=curNode.x[0]+offset[i][0];
			tmp.y[0]=curNode.y[0]+offset[i][1];
			if(!is_ok(tmp.x[0],tmp.y[0])||s[tmp.x[0]][tmp.y[0]]=='#')
				continue;//越界 或 是障碍物
			for(int j=0;j<4;++j){
				tmp.x[1]=curNode.x[1]+offset[j][0];
				tmp.y[1]=curNode.y[1]+offset[j][1];
				if(!is_ok(tmp.x[1],tmp.y[1])||s[tmp.x[1]][tmp.y[1]]=='#')
					continue;// 越界 或 是障碍物 
				tmp.status=(curNode.status|(1<<(tmp.x[0]*m+tmp.y[0])))|
										   (1<<(tmp.x[1]*m+tmp.y[1]));
				if(vis[tmp.x[0]][tmp.y[0]][tmp.x[1]][tmp.y[1]][tmp.status]>0)
					continue;
				vis[tmp.x[0]][tmp.y[0]][tmp.x[1]][tmp.y[1]][tmp.status]=
				    vis[curNode.x[0]][curNode.y[0]][curNode.x[1]][curNode.y[1]][curNode.status]+1;
				q.push(tmp);
			}
		}
	}

}
int main(){
	for(int i=0;i<n;++i)
		scanf("%s",s[i]);
	int sx,sy;
	for(int i=0;i<n;++i)
		for(int j=0;j<m;++j)
			if(s[i][j]=='S'){
				sx=i;
				sy=j;
				finish|=1<<(i*m+j);
			}else if(s[i][j]=='.')
				finish|=1<<(i*m+j);
	cout<<bfs(sx,sy)<<endl;
	return 0;
}

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).