maze

C++14(g++5.4) 解法, 执行用时: 103ms, 内存消耗: 1508K, 提交时间: 2020-06-27 21:26:34

using namespace std;
#include<iostream>
#include<queue>
#include<cstring>
#include<cmath>
char mp[305][305];
int vis[305][305];
int turn[305][305];
int sx,sy,tx,ty,n,m,q;
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
struct node{
	int x,y;
	int t;
};
queue<node> qu;

int main(){
	while(cin>>n>>m>>q){
		memset(vis,0,sizeof(vis));
		memset(mp,0,sizeof(mp));
		memset(turn,0,sizeof(turn));
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				cin>>mp[i][j];
				if(mp[i][j]=='S'){
					sx=i;
					sy=j;
				}
				if(mp[i][j]=='T'){
					tx=i;
					ty=j;
				}
			}
		}
		int x1,y1,x2,y2;
		for(int i=0;i<q;i++){
			cin>>x1>>y1>>x2>>y2;
			turn[x1+1][y1+1]=x2*n+y2; 
		}
	int ans=0x3f3f3f;
	bool flag=0;
	qu.push({sx,sy,0});
	vis[sx][sy]=1;
	while(!qu.empty()){
		node tmp=qu.front();
		qu.pop();
		if(mp[tmp.x][tmp.y]=='#') continue;
		if(tmp.x==tx&&tmp.y==ty){
			ans=min(ans,tmp.t);
			flag=1;
			continue;
		}
		if(turn[tmp.x][tmp.y]){
			int tmpp=turn[tmp.x][tmp.y];
			qu.push({tmpp/n+1,tmpp%n+1,tmp.t+3});
		}
		for(int i=0;i<4;i++){
			int dx=tmp.x+dir[i][0];
			int dy=tmp.y+dir[i][1];
		    if(dx<1||dx>n||dy<1||dy>m||vis[dx][dy]==1) continue;
			vis[dx][dy]=1;
			qu.push({dx,dy,tmp.t+1});	
		}
	}
	if(flag) cout<<ans<<endl;
	else cout<<-1<<endl;
	}
	return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 291ms, 内存消耗: 1044K, 提交时间: 2023-04-25 11:58:07

#include<bits/stdc++.h>
using namespace std;
const int N=310;
char g[N][N];
bool bo[N][N];
int d[4][2]={0,1,0,-1,1,0,-1,0};
typedef pair<int,int>PII; 
struct dis
{
	int su;
	int x,y;
	 bool operator< (const dis &b) const  
     {
            return su > b.su;
      }
};
int main()
{
	int n,m,q;
	
	while(cin>>n>>m>>q)
	{
		memset(g,0,sizeof g);
		memset(bo,0,sizeof bo);
		priority_queue<dis> qu;
		map<PII,PII> cs; 
		
		for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
		{
			cin>>g[i][j];
			if(g[i][j]=='S')
			{
			qu.push({0,i,j});
			}
		}
		
	   for(int i=0;i<q;i++)
	   {  
	      int x,y,a,b;
		  cin>>x>>y>>a>>b;
          cs[{x,y}]={a,b};
	   }
   while(qu.size())
	{
		int sz=qu.size();
		for(int i=0;i<sz;i++)
		{
			auto p=qu.top();
			qu.pop();
			int dist=p.su;
			int x=p.x;
			int y=p.y;
			
			if(bo[x][y])continue;
			bo[x][y]=1;
			
			if(g[x][y]=='T')
			{
		  	cout<< dist<<endl;
			  goto f;	
			}
			
			if(cs.find({x,y})!=cs.end())
			{
				PII pi=cs[{x,y}];
				if(g[pi.first][pi.second]!='#')
				qu.push({dist+3,pi.first,pi.second});
			}
			for(int j=0;j<4;j++)
			{
				int x1=d[j][0]+x;
				int y1=d[j][1]+y;
				if(x1>=0&&x1<n&&y1>=0&&y1<m&&g[x1][y1]!='#')
				qu.push({dist+1,x1,y1});
			}
		}
	}
	 cout<<-1<<endl;
	 f:;
	}
}

C++11(clang++ 3.9) 解法, 执行用时: 57ms, 内存消耗: 5580K, 提交时间: 2020-05-13 14:52:25

#include<bits/stdc++.h>
using namespace std;

struct node
{
	int x,y,h;
}Q[100005];
struct node1
{
	int x,y;
}s;
vector<node1>T[305][305];
int r,f,V[305][305],dx[]={0,0,1,-1},dy[]={1,-1,0,0};
char R[305][305];
int main()
{
    int i,j,n,m,q,x,y,h,X,Y,ans;
    while(~scanf("%d%d%d",&n,&m,&q))
    {
		ans=1e9,r=1,f=0;
		for(i=0;i<n;i++)scanf("%s",R[i]);
		for(i=0;i<n;i++)
            for(j=0;j<m;j++)
            {
            	T[i][j].clear(),V[i][j]=1e9;
				if(R[i][j]=='S')Q[0].x=i,Q[0].y=j,V[i][j]=Q[0].h=0;
			}
        while(q--)scanf("%d%d%d%d",&X,&Y,&s.x,&s.y),T[X][Y].push_back(s);
	    while(r!=f)
	    {
	    	x=Q[f].x,y=Q[f].y,h=Q[f++].h;
	    	if(R[x][y]=='T'){ans=min(ans,h);continue;} 
	    	for(i=0;i<T[x][y].size();i++)
	    	{
	    		X=T[x][y][i].x,Y=T[x][y][i].y;
	    		if(R[X][Y]=='#'||V[X][Y]<=h+3)continue;
	    		Q[r].x=X,Q[r].y=Y,Q[r++].h=V[X][Y]=h+3;
			}
			for(i=0;i<4;i++)
			{
				X=x+dx[i],Y=y+dy[i];
				if(X<0||X>=n||Y<0||Y>=m||V[X][Y]<=h+1||R[X][Y]=='#')continue;
				Q[r].x=X,Q[r].y=Y,Q[r++].h=V[X][Y]=h+1;
			}
		}
		if(ans==1e9)ans=-1;
		printf("%d\n",ans);
	}
	return 0;
}

pypy3 解法, 执行用时: 1275ms, 内存消耗: 45756K, 提交时间: 2021-06-06 19:10:23

from collections import deque

while True:
	try:
		n, m, q = map(int, input().split())
		a = [input().strip() for _ in range(n)]
		p = {}
		for _ in range(q):
			x1, y1, x2, y2 = map(int, input().split())
			p[(x1, y1)] = (x2, y2)
		s, t, dist = None, None, {}
		for i in range(n):
			for j in range(m):
				if a[i][j] == 'S': s = (i, j)
				elif a[i][j] == 'T': t = (i, j)
		q = deque()
		q.append(s)
		dist[s] = 0
		while q:
			i, j = q.popleft()
			for (x, y) in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
				if x < 0 or x >= n or y < 0 or y >= m or a[x][y] == '#': continue
				if (x, y) not in dist or dist[(x, y)] > dist[(i, j)] + 1:
					dist[(x, y)] = dist[(i, j)] + 1
					q.append((x, y))
				if (i, j) in p and a[p[(i, j)][0]][p[(i, j)][1]] != '#':
					if p[(i, j)] not in dist or dist[p[(i, j)]] > dist[(i, j)] + 3:
						dist[p[(i, j)]] = dist[(i, j)] + 3
						q.append(p[(i, j)])
		print(dist.get(t, -1))
	except:
		break

详情