目录

P1332 血色先锋队

173. 矩阵距离

P1162 填涂颜色

P1506 拯救oibh总部

P2895 [USACO08FEB] Meteor Shower S

P3395 路障 

---

P1332 血色先锋队

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int dis[600][600];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, -1, 0, 1};
int n, m, a, b;
queue<pair<int, int>> q;
void bfs()
{while (!q.empty()){auto t = q.front();q.pop();for (int i = 0; i < 4; i++){int nx = t.first + dx[i];int ny = t.second + dy[i];if (nx >= 1 && ny >= 1 && nx <= n && ny <= m && dis[nx][ny] == -1){q.push({nx, ny});dis[nx][ny] = dis[t.first][t.second] + 1;}}}
}
int main()
{cin >> n >> m;cin >> a >> b;memset(dis, -1, sizeof dis);while (a--){int x, y;cin >> x >> y;dis[x][y] = 0;q.push({x, y});}bfs();while (b--){int x, y;cin >> x >> y;cout << dis[x][y] << endl;}return 0;
}

173. 矩阵距离

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int dis[1010][1010];
char s[1010][1010];
int n, m;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, -1, 0, 1};
queue<pair<int, int>> q;
void bfs()
{while (!q.empty()){auto t = q.front();q.pop();for (int i = 0; i < 4; i++){int nx = t.first + dx[i];int ny = t.second + dy[i];if (nx >= 1 && ny >= 1 && nx <= n && ny <= m && dis[nx][ny] == -1){q.push({nx, ny});dis[nx][ny] = dis[t.first][t.second] + 1;}}}
}
int main()
{cin >> n >> m;memset(dis, -1, sizeof dis);for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){cin >> s[i][j];if (s[i][j] == '1'){dis[i][j] = 0;q.push({i, j});}}}bfs();for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){cout << dis[i][j] << " ";}cout << endl;}return 0;
}

 

P1162 填涂颜色

#include <iostream>
#include <queue>
using namespace std;
bool vis[50][50];
int a[50][50];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, -1, 0, 1};
int n;
queue<pair<int, int>> q;
void bfs(int x, int y)
{q.push({x, y});while (!q.empty()){auto t = q.front();q.pop();for (int i = 0; i < 4; i++){int nx = t.first + dx[i];int ny = t.second + dy[i];if (nx >= 0 && ny >= 0 && nx <= n + 1 && ny <= n + 1 && a[nx][ny] == 0 && !vis[nx][ny]){vis[nx][ny] = true;q.push({nx, ny});}}}
}
int main()
{cin >> n;for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){cin >> a[i][j];}}bfs(0, 0);for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){if (vis[i][j] == false && a[i][j] == 0){a[i][j] = 2;}cout << a[i][j] << " ";}cout << endl;}return 0;
}

P1506 拯救oibh总部

#include <iostream>
#include <queue>
using namespace std;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, -1, 0, 1};
queue<pair<int, int>> q;
bool vis[510][510];
char s[510][510];
int n, m;
int res;
void bfs(int x, int y)
{q.push({x, y});while (!q.empty()){auto t = q.front();q.pop();for (int i = 0; i < 4; i++){int nx = t.first + dx[i];int ny = t.second + dy[i];if (nx >= 0 && ny >= 0 && nx <= n + 1 && ny <= m + 1 && s[nx][ny] != '*' && !vis[nx][ny]){vis[nx][ny] = true;q.push({nx, ny});}}}
}
int main()
{cin >> n >> m;for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){cin >> s[i][j];}}bfs(0, 0);for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){if (s[i][j] == '0' && vis[i][j] == false){res++;}}}cout << res;return 0;
}

P2895 [USACO08FEB] Meteor Shower S

#include <iostream>
#include <queue>
#include <climits>
#include <cstring>
using namespace std;
int fire[310][310];
int dis[310][310];
int dx[] = {1, 0, -1, 0, 0};
int dy[] = {0, -1, 0, 1, 0};
int m;
queue<pair<int, int>> q;
int bfs()
{memset(dis, -1, sizeof dis);q.push({0, 0});dis[0][0] = 0;while (!q.empty()){auto t = q.front();q.pop();for (int i = 0; i < 4; i++){int nx = t.first + dx[i];int ny = t.second + dy[i];int nt = dis[t.first][t.second] + 1;if (nx >= 0 && ny >= 0 && nx <= 301 && ny <= 301 && dis[nx][ny] == -1){if (nt < fire[nx][ny]){q.push({nx, ny});dis[nx][ny] = nt;if (fire[nx][ny] == INT_MAX){return dis[nx][ny];}}}}}return -1;
}
int main()
{cin >> m;for (int i = 0; i <= 301; i++){for (int j = 0; j <= 301; j++){fire[i][j] = INT_MAX;}}while (m--){int x, y, t;cin >> x >> y >> t;for (int i = 0; i < 5; i++){int nx = x + dx[i];int ny = y + dy[i];if (nx >= 0 && ny >= 0 && nx <= 301 && ny <= 301 && fire[nx][ny] > t){fire[nx][ny] = t;}}}int res = bfs();cout << res;return 0;
}

P3395 路障 

#include <iostream>
#include <cstring>
#include <queue>
#include <climits>
using namespace std;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, -1, 0, 1};
int fire[1010][1010];
int dis[1010][1010];
int n;
bool bfs()
{queue<pair<int, int>> q; // 队列不能设置为全局变量，因为有多组数据memset(dis, -1, sizeof dis);q.push({1, 1});dis[1][1] = 0;// 注意n有可能等于1if (n == 1){return true;}while (!q.empty()){auto t = q.front();q.pop();for (int i = 0; i < 4; i++){int nx = t.first + dx[i];int ny = t.second + dy[i];int nt = dis[t.first][t.second] + 1;if (nx >= 1 && ny >= 1 && nx <= n && ny <= n && nt <= fire[nx][ny] && dis[nx][ny] == -1){q.push({nx, ny});dis[nx][ny] = nt;if (nx == n && ny == n){return true;}}}}return false;
}
void solve()
{cin >> n;for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){fire[i][j] = INT_MAX;}}int t = 1;for (int i = 1; i <= n * 2 - 2; i++){int x, y;cin >> x >> y;fire[x][y] = min(fire[x][y], t++);}bool res = bfs();if (!res){cout << "No" << endl;}else{cout << "Yes" << endl;}
}
int main()
{int t;cin >> t;while (t--){solve();}return 0;
}