题目链接在这里:
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");
else
puts("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");
else
puts("No");
}
}
return 0;
}
DFS BFS都错,,我也太渣了,请高手赐教!!
PHP中文网2017-04-17 15:37:58
Looking at the example is not a search at all.
As long as the position of "Headquarters" is not higher than the given "water release" position, it will be flooded.
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';
}
}