help! 营救计划 RE 0

常规
1 
#include<bits/stdc++.h>
using namespace std;
queue<int>x,x1;
int vis[1001][1001],ans[1001][1001]={-1};
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
char a[1140][1140];
int main(){
	int n,m,start_x,start_y,fx,fy;
	cin>>n>>m;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>a[i][j];
			if(a[i][j]='M'){
				fx=i;
				fy=j;
			}else if(a[i][j]='@'){
				start_x=i;
				start_y=j;
			}
		}
	}
	x.push(start_x);
	x1.push(start_y);
	ans[start_x][start_y]=0;
	vis[start_x][start_y]=1;
	while(!x.empty()){
		for(int i=0;i<4;i++){
			int next_x=x.front()+dx[i];
			int next_y=x1.front()+dy[i];
			if((next_x>0&&next_x<=n)&&(next_y>0&&next_y<=m)&&vis[next_x][next_y]==0&&(a[next_x][next_y]=='.'||a[next_x][next_y]=='G')){
				vis[next_x][next_y]=1;
				if(a[next_x][next_y]=='G') ans[next_x][next_y]=ans[x.front()][x1.front()]+2;
				else ans[next_x][next_y]=ans[x.front()][x1.front()]+1;
				x.push(next_x);
				x1.push(next_y);
			}
		}
		x.pop();
		x1.pop();
	}
	if(ans[fx][fy]==-1) cout<<"You can't save Mengxin";
	else cout<<ans[fx][fy];
	return 0;
}
1 个赞
2

题目:

C. 营救计划

Problem ID: 3585

Contest ID: 5350

选做题

Runtime Error

时间限制：0.2s 空间限制：128M

题目描述：

在一个 n∗m 的迷宫里，有一个萌新被困住了，你作为一个久经码场的战士，决定去营救萌新。地图中还会有一些守卫，你必须打败守卫才能通过守卫所在的位置，打败守卫需要花费 1 分钟，移动一步也需要花费 1 分钟，每次你只能往上下左右某个方向移动一步。问你最少需要花费多少时间才能救到萌新。

输入格式：

第一行输入两个整数 n,m。(1≤n,m≤1000)

接下来 n 行每行输入 m 个字符

‘#’ 代表障碍物，无法直接通过

‘.’ 代表空地，可以直接通过

‘G’ 代表守卫，你需要打败他才能通过

‘M’ 代表萌新所在的位置

‘@’ 表示你所在的位置

输出格式：

如果可以营救到萌新，就输出最少需要花费的分钟数

如果不可以，则输出 “You can’t save Mengxin”

样例输入1：

7 8 #.#####. #.M#…@. #…#G… …#…#.# #…##… .#… …

样例输出1：

13

样例输入2：

2 2 M. G@

样例输出2：

2

1 个赞
3

改一下思路吧，我用的是结构体+列表，然后用flag变量做标记
源码贴在下面 :point_down:

struct node{
    int x,y,step;
}arr[10005],st,ed,now,nxt;
char mp[1005][1005];
int vis[1005][1005];
int dir[4][2]={0,1,0,-1,1,0,-1,0};
bool operator < (node a,node b){
    return b.step < a.step;
}
int main(){
    int n,m,t,flag;
    flag=0;
    priority_queue<node>q;
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        cin >> mp[i]+1;
        for(int j=1;j<=m;j++){
            if(mp[i][j]=='@'){
                st.x=i,st.y=j; 
            }
            if(mp[i][j]=='M'){
                ed.x=i,ed.y=j;
            }
        }
    }
    st.step=0;
    q.push(st);
    vis[st.x][st.y]=1;
    while(q.size()){
        now=q.top();
        if(now.x==ed.x&&now.y==ed.y){
            cout << now.step << endl;
            flag=1;
            break;
        }
        for(int i=0;i<4;i++){
            nxt=now;
            nxt.x+=dir[i][0];
            nxt.y+=dir[i][1];
            if(nxt.x>=1&&nxt.x<=n&&nxt.y>=1&&nxt.y<=m&&!vis[nxt.x][nxt.y]&&mp[nxt.x][nxt.y]!='#'){
                if(mp[nxt.x][nxt.y]=='G'){
                    nxt.step+=2;
                }else nxt.step+=1;
                q.push(nxt);
                vis[nxt.x][nxt.y]=1;
            } 
        }
        q.pop();
    }
    if(!flag){
        cout << "You can't save Mengxin";
    }
    return 0;
}
1 个赞