问题描述
题目链接在这里：
https://acm.bnu.edu.cn/bnuoj/...
从网上看的题解都是BFS的，自己写了一个DFS的，总是不对，不知何故，请高手赐教！谢谢了！！
#include<stdio.h>#include<iostream>#include<string.h>#include<algorithm>using namespace std;int t, m, n;int map[205][205];int mark[205][205];int go[4][2] ={ 0,1, 0,-1, 1,0, -1,0};void DFS(int a, int b){ for (int i = 0; i < 4; i++) {int aa = a + go[i][0];int bb = b + go[i][1];if (aa<1 || aa>m || bb<1 || bb>n) continue;if (mark[aa][bb] == 1){ map[aa][bb] = max(map[aa][bb], map[a][b]); continue;}if (map[aa][bb] <= map[a][b]){ mark[aa][bb] = 1; map[aa][bb] = map[a][b]; DFS(aa, bb);} }}int main(){ while (scanf('%d', &t) != EOF) {while (t--){ scanf('%d%d', &m, &n); for (int i = 1; i <= m; i++)for (int j = 1; j <= n; j++) scanf('%d', &map[i][j]); int mm, nn; scanf('%d%d', &mm, &nn); int x; scanf('%d', &x); memset(mark, 0, sizeof(mark)); while (x--) {int a, b;scanf('%d%d', &a, &b);mark[a][b] = 1;DFS(a, b); } if (mark[mm][nn] == 1)puts('Yes'); elseputs('No');} } return 0;}
然后我又写了一个BFS，还是不对
#include<stdio.h>#include<iostream>#include<queue>#include<algorithm>#include<string.h>using namespace std;struct state{ int x, y;};int go[4][2]={ 0,1, 0,-1, 1,0, -1,0};int map[205][205];int mark[205][205];int m, n;queue<state> q;bool BFS(int x, int y){ while (!q.empty()) {state s = q.front();q.pop();for (int i = 0; i < 4; i++){ int xx = s.x + go[i][0]; int yy = s.y + go[i][1]; if (xx<1 || xx>m || yy<1 || yy>n)continue; if (mark[xx][yy] == 1)continue; if (map[xx][yy] > map[s.x][s.y])continue; state tmp; tmp.x = xx; tmp.y = yy; mark[xx][yy] = 1; q.push(tmp);if (xx == x && yy == y)return true;} } return false;}int main(){ int t; //freopen('my.in', 'r', stdin); while (scanf('%d', &t) != EOF) {while (t--){ scanf('%d%d', &m, &n); for (int i = 1; i <= m; i++)for (int j = 1; j <= n; j++) scanf('%d', &map[i][j]); int mm, nn; scanf('%d%d', &mm, &nn); int x; scanf('%d', &x); memset(mark, 0, sizeof(mark)); while (!q.empty())q.pop(); while (x--) {int a, b;scanf('%d%d', &a, &b);mark[a][b] = 1;state s;s.x = a;s.y = b;q.push(s); } if (BFS(mm,nn))puts('Yes'); elseputs('No');} } return 0;}
DFS BFS都错，，我也太渣了，请高手赐教！！
问题解答
回答1：看样例根本不是搜索吧.
是'司令部'的位置只要不高于给出的'放水'的位置就被淹了.
AC 176ms
#include<iostream>#include<cstring>using namespace std;const int SIZE = (200 + 10);int g[ SIZE ][ SIZE ];struct node { int x, y; node(int t_x = -1, int t_y = -1):x(t_x), y(t_y) { }}start;int main() { int T; cin >> T; while (T--) {int col, row;cin >> row >> col;for (int i = 0; i<row; i++) for (int j = 0; j<col; j++)cin >> g[ i ][ j ];int x, y;cin >> x>> y;start = node(x - 1, y - 1);int m;cin >> m;bool flag = false;while (m--) { cin >> x >> y; if (g[ start.x ][ start.y ] <= g[ x-1 ][ y-1 ])flag = true;}if (flag)cout << 'Yes';else cout << 'No';cout << ’n’; }}
