刺杀大使

一道并不难的二分题，竟让我交了上20次，诶，果然还是我太弱了。

看完题目就基本想到要怎么做了：

只需要对最小伤害代价进行二分即可，check()函数里用搜索判断是否可以到达最后一行，这里的check()用深搜广搜都可以，两种的代码下面都会给出，而经过检验，这道题目用深搜会优于广搜。

如果你不像我一般手滑的话，此题基本就可以过了。

然而，导致我反复提交20遍的原因，不是二分答案时卡循环的问题，而是，，，

数组开小了

这也给我提了个醒，不是所有的re都是二分循环的锅，有时候要考虑数组越界的问题。

用汝佳julao的话说，就是 : 编写一个尽量鲁棒的程序！！！

code:

深搜做法（更优）：

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

//Mystery_Sky

//

#define M 2000

#define INF 0x7f7f7f7f

const int dx[] = {0, 0, 1, -1};

const int dy[] = {1, -1, 0, 0};

int l, r, mid;

bool vis[M][M], flag;

int n, m, a[M][M];

void check(int x, int y, int ans)

{

	if(x == n)	{

		flag = true;

	}

	for(int i = 0; i <= 3; i++) {

		int xx = x + dx[i];

		int yy = y + dy[i];

		if(xx <= 0 || yy <= 0 || xx > n || yy > m || a[xx][yy] > ans || vis[xx][yy]) continue;

		vis[xx][yy] = 1;

		check(xx, yy, ans);

		if(flag) return;

	}

}

int main() {

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

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

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

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

	l = 0;

	while(l <= r) {

		mid = (l+r)/2;

		memset(vis, 0, sizeof(vis));

		flag = 0;

		check(1, 1, mid);

		if(flag) r = mid - 1;

		else l = mid + 1;

	}

	printf("%d\n", l);

	return 0;

}

广搜做法：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

using namespace std;

//Mystery_Sky

//

#define M 2000

#define INF 0x7f7f7f7f

struct node{

    int x, y;

};

int n, m, p[M][M];

int l, r, mid, maxx;

int vis[M][M];

int dx[] = {0, 0, 1, -1};

int dy[] = {1, -1, 0, 0};

int Ans;

inline bool check(int ans)

{

    memset(vis, 0, sizeof(vis));

    queue <node> q;

    q.push((node){1, 1});

    while(!q.empty()) {

        node top = q.front();

        q.pop();

        int x, y;

        for(int i = 0; i <= 3; i++) {

                x = top.x + dx[i];

                y = top.y + dy[i];

                if(x <= 0 || y <= 0 || x > n || y > m || p[x][y] > ans || vis[x][y]) continue;

                vis[x][y] = 1;

                q.push((node){x, y});

                if(x == n)	return true;

        }

    }

    return false;

}

int main() {

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

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

        for(int j = 1; j <= m; j++) scanf("%d", &p[i][j]);

    l = 0, r = 1024;

    while(l < r) {

        mid = (l+r)>>1;

        if(check(mid)) {

            r = mid;

        }

        else l = mid+1;

    }

    printf("%d\n", l);

    return 0;

}

巴特西

洛谷 P1902 刺杀大使

刺杀大使

一道并不难的二分题，竟让我交了上20次，诶，果然还是我太弱了。

看完题目就基本想到要怎么做了：

只需要对最小伤害代价进行二分即可，check()函数里用搜索判断是否可以到达最后一行，这里的check()用深搜广搜都可以，两种的代码下面都会给出，而经过检验，这道题目用深搜会优于广搜。

用汝佳julao的话说，就是 : 编写一个尽量鲁棒的程序！！！

code:

深搜做法（更优）：

广搜做法：

最新文章

热门文章