- 问答
洛谷P1514
- 2023-10-11 21:33:49 @
https://www.luogu.com.cn/problem/P1514 一直做不对
#include <bits/stdc++.h>
using namespace std;
queue<pair<int, int> > q;
const int T = 5100;
int M, N;
int cnt;
int m[T][T];
bool bm[T][T];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};
void bfs(int x, int y)
{
if(!q.empty())
{
for(int i = 0; i < 4; i++)
{
if(x + dx[i] >= 1 && x + dx[i] <= M && y + dy[i] >= 1 && y + dy[i] <= N && m[y][x] > m[y + dy[i]][x + dx[i]] && bm[y + dy[i]][x + dx[i]] == false)
{
q.push(make_pair(x + dx[i], y + dy[i]));
cout << y + dy[i] << " "<< x + dx[i] << endl;
bm[y + dy[i]][x + dx[i]] = true;
cnt ++;
}
}
pair<int, int>p;
p = q.front();
q.pop();
bfs(x + p.first, y + p.second);
}
}
bool cmp(int a, int b)
{
return a > b;
}
int main()
{
int m_x[T];
int m_x_c[T];
cin >> N >> M;
for(int i = 1; i <= N; i++)
{
for(int j = 1; j <= M; j++)
{
cin >> m[i][j];
if(i == 1)
{
m_x[j] = m[i][j];
m_x_c[j] = m[i][j];
}
}
}
sort(m_x + 1, m_x + 1 + M, cmp);
//for(int i = 1; i <= M; i++)
//cout << m_x[i] << " ";
//cout << endl;
for(int i = 1; i <= M; i++)
{
int h = 0;
for(int j = 1; j <= M; j++)
{
if(m_x[i] == m_x_c[j])
{
h = j;
break;
}
}
//cout << h << endl;
if(bm[1][i] == true)
continue;
//cout << i << endl;
q.push(make_pair(1,h));
bfs(h, 1);
cnt ++;
if(cnt == M * N)
{
cout << 1 << endl << i;
return 0;
}
}
int k = 0;
//cout << cnt << endl;
for(int i = 1; i <= M; i++)
{
if(bm[N][i] == false)
k ++;
}
cout << 0 << endl << k;
return 0;
}
0 comments
No comments so far...