BFS 第一个点TLE 88
  • 板块P2802 回家
  • 楼主tlyy11
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/1/26 14:52
  • 上次更新2024/1/26 16:57:58
查看原帖
BFS 第一个点TLE 88
905019
tlyy11楼主2024/1/26 14:52
#include<bits/stdc++.h>
using namespace std;
long long a[11][11], dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
int tx, ty, lx, ly, n, m, mou = 6, t = 0, minn = 1 << 30;
void dfs(int x, int y, int mou){
	if(mou == 0 || t > m * n || t > minn){
        return;
    }
	if(a[x][y] == 4){
        mou = 6;
    }
    if(x == lx && y == ly){
        minn = min(t, minn);
    } else{
        for (int i = 0; i < 4; i++){
            tx = x + dir[i][0];
            ty = y + dir[i][1];
            if(tx <= 0 || tx > n || ty <= 0 || ty > m || a[tx][ty] == 0){
            	continue;
			}
            ++t;
            dfs(tx, ty, mou - 1);
			--t;
        }
    }
}
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
    	for(int j = 1; j <= m; j++){
            cin >> a[i][j];
            if(a[i][j] == 2){
                tx = i;
				ty = j; 
            }
            if(a[i][j] == 3){
                lx = i;
				ly = j;
            }
        }
	}
    dfs(tx, ty, mou);
    if(minn != 1<<30){
    	cout << minn << endl;
	} else {
		cout << -1 << endl;
	}
    return 0;
} 

 
2024/1/26 14:52
加载中...