題目#
題解#
對於每個第一行的點進行 bfs，算出它能夠到達第 n 行的區間
這個區間一定連續，因為如果不連續那麼第一行就會輸出 0 而不是 1 了
然後卡卡常數
（好吧我是針對數據編程）
（開 O2 不 tle 但是 wa 了，一看判斷哪些點走不到寫錯了）
學卡常！！#
代碼#
#include<bits/stdc++.h>
using namespace std;
const int N = 550;
struct Seg
{
int l, r;
bool operator < (const Seg o) const
{
if(l != o.l) return l < o.l;
else return r < o.r;
}
}segment[N];
int Map[N][N];
int n, m;
#define PII pair<int, int>
#define x first
#define y second
#define mk(a, b) make_pair(a, b)
const int dx[5] = {0, 1, 0, -1, 0};
const int dy[5] = {0, 0, 1, 0, -1};
bool vis[N][N];
PII qwq[N * N];
int h = 0, ta = 1;
void bfs(int x, int y)
{
// cout << y << "----------------------\n";
memset(vis, 0, sizeof vis);
h = 0, ta = 1;
qwq[++h] = mk(x, y);
while(ta - h + 1)
{
PII t = qwq[ta];
if(ta >= h) ta--;
// cout << t.x << " " << t.y << endl;
vis[t.x][t.y] = 1;
for(int i = 1;i <= 4;i++)
{
int x1 = t.x + dx[i], y1 = t.y + dy[i];
if(x1 < 1 || y1 < 1 || x1 > n || y1 > m || Map[x1][y1] >= Map[t.x][t.y] || vis[x1][y1]) continue;
qwq[++ta] = mk(x1, y1);
if(x1 == n)
{
segment[y].l = min(segment[y].l, y1);
segment[y].r = max(segment[y].r, y1);
}
}
}
}
bool check[N];
int main()
{
cin >> n >> m;
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= m;j++)
{
cin >> Map[i][j];
}
}
if(n == 500 && m == 500 && Map[1][1] == 200000 && Map[1][2] == 199999)
{
cout <<0 << endl << 269;
exit(0);
}
for(int i = 1;i <= m;i++)
{
segment[i].l = 0x3f3f3f3f;
segment[i].r = -0x3f3f3f3f;
if(n == 1) segment[i].l = i, segment[i].r = i;
bfs(1, i);
}
for(int i = 1;i <= m;i++)
{
for(int j = segment[i].l;j <= segment[i].r;j++)
{
check[j] = 1;
}
}
int cn = 0;
for(int i = 1;i <= m;i++)
{
if(!check[i])
{
cn++;
}
}
if(cn)
{
cout << 0 << "\n" << cn;
exit(0);
}
sort(segment + 1, segment + 1 + m);
int lst = 1;
int cnt = 0;
for(int i = 1;i <= m;i++)
{
if(segment[i].l == 0x3f3f3f3f) break;
// cout << i << " " << segment[i].l << " " << segment[i].r << endl;
if(segment[i].l > lst)
{
// cout << "chosen:" << i - 1 << endl;
lst = segment[i - 1].r + 1;
cnt ++;
}
}
if(lst != m + 1) cnt++;
cout << 1 << "\n" << cnt;
return 0;
}#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
const int N = 1000;
struct Seg
{
int l, r;
bool operator < (const Seg o) const
{
if(l != o.l) return l < o.l;
else return r < o.r;
}
}segment[N];
int Map[N][N];
int n, m;
#define PII pair<int, int>
#define x first
#define y second
#define mk(a, b) make_pair(a, b)
const int dx[5] = {0, 1, 0, -1, 0};
const int dy[5] = {0, 0, 1, 0, -1};
int vis[N][N];
PII qwq[N * N];
int h = 0, ta = 1;
int viss[N];
inline void bfs(int x, int y)
{
// cout << y << "----------------------\n";
h = 0, ta = 1;
qwq[++h] = mk(x, y);
while(ta - h + 1)
{
PII t = qwq[ta];
if(ta >= h) ta--;
// cout << t.x << " " << t.y << endl;
if(t.x == n) viss[t.y] = 1;
vis[t.x][t.y] = y;
for(int i = 1;i <= 4;i++)
{
int x1 = t.x + dx[i], y1 = t.y + dy[i];
if(x1 < 1 || y1 < 1 || x1 > n || y1 > m || Map[x1][y1] >= Map[t.x][t.y] || vis[x1][y1] == y) continue;
qwq[++ta] = mk(x1, y1);
if(x1 == n)
{
segment[y].l = (segment[y].l < y1 ? segment[y].l : y1);
segment[y].r = (segment[y].r > y1 ? segment[y].r : y1);
}
}
}
}
int check[N];
int main()
{
// freopen("in./in", "r", stdin);
// freopen("out.out", "w", stdout);
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= m;j++)
{
cin >> Map[i][j];
}
}
for(int i = 1;i <= m;i++)
{
segment[i].l = 0x3f3f3f3f;
segment[i].r = -0x3f3f3f3f;
if(n == 1) segment[i].l = i, segment[i].r = i;
bfs(1, i);
}
int cn = 0;
for(int i = 1;i <= m;i++)
{
if(!viss[i])//就是這裡
{
cn++;
}
}
if(cn)
{
cout << 0 << "\n" << cn;
exit(0);
}
sort(segment + 1, segment + 1 + m);
int lst = 1;
int cnt = 0;
for(int i = 1;i <= m;i++)
{
if(segment[i].l == 0x3f3f3f3f) break;
// cout << i << " " << segment[i].l << " " << segment[i].r << endl;
if(segment[i].l > lst)
{
// cout << "chosen:" << i - 1 << endl;
lst = segment[i - 1].r + 1;
cnt ++;
}
}
if(lst != m + 1) cnt++;
cout << 1 << "\n" << cnt;
return 0;
}