|
|
|
|
讨论 Discussion |
|
| |
 ffff |
#include <iostream>
using namespace std;
const int MAX_N = 1005;
char maze[MAX_N][MAX_N];
int visited[MAX_N][MAX_N];
int component_size[MAX_N * MAX_N];
int component_id = 0;
int n, m;
struct Node {
int x, y;
Node* next;
};
class Queue {
private:
Node* front;
Node* rear;
public:
Queue() : front(nullptr), rear(nullptr) {}
void push(int x, int y) {
Node* newNode = new Node {x, y, nullptr};
if (rear == nullptr) {
front = rear = newNode;
} else {
rear->next = newNode;
rear = newNode;
}
}
void pop() {
if (front == nullptr) return;
Node* temp = front;
front = front->next;
if (front == nullptr) rear = nullptr;
delete temp;
}
pair<int, int> getFront() {
return {front->x, front->y};
}
bool empty() {
return front == nullptr;
}
};
bool isValid(int x, int y) {
return x >= 1 && x <= n && y >= 1 && y <= n;
}
void bfs(int start_x, int start_y) {
if (visited[start_x][start_y] != 0) {
return;
}
component_id++;
int count = 0;
Queue q;
q.push(start_x, start_y);
visited[start_x][start_y] = component_id;
while (!q.empty()) {
int x = q.getFront().first;
int y = q.getFront().second;
q.pop();
count++;
char current = maze[x][y];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (isValid(nx, ny) && visited[nx][ny] == 0) {
if ((current == '0' && maze[nx][ny] == '1') ||
(current == '1' && maze[nx][ny] == '0')) {
visited[nx][ny] = component_id;
q.push(nx, ny);
}
}
}
}
component_size[component_id] = count;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> maze[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (visited[i][j] == 0) {
bfs(i, j);
}
}
}
for (int k = 0; k < m; k++) {
int i, j;
cin >> i >> j;
cout << component_size[visited[i][j]] << endl;
}
return 0;
}
( ) |
| 22 |
#include <iostream>
using namespace std;
const int MAX_N = 100;
int path[MAX_N];
int n;
void dfs(int remaining, int start, int depth) {
if (remaining == 0) {
if (depth > 1) {
for (int i = 0; i < depth; i++) {
cout << path[i];
if (i < depth - 1) {
cout << "+";
}
}
cout << endl;
}
return;
}
for (int i = start; i <= remaining; i++) {
path[depth] = i;
dfs(remaining - i, i, depth + 1);
}
}
int main() {
freopen("p1552.in","r",stdin);
freopen("p1552.out","w",stdout);
cin >> n;
dfs(n, 1, 0);
fclose(stdin);
fclose(stdout);
return 0;
}
( )
|
| 22 |
#include <iostream>
using namespace std;
const int MAX_N = 100;
int path[MAX_N];
int n;
void dfs(int remaining, int start, int depth) {
if (remaining == 0) {
if (depth > 1) {
for (int i = 0; i < depth; i++) {
cout << path[i];
if (i < depth - 1) {
cout << "+";
}
}
cout << endl;
}
return;
}
for (int i = start; i <= remaining; i++) {
path[depth] = i;
dfs(remaining - i, i, depth + 1);
}
}
int main() {
freopen("p1552.in","r",stdin);
freopen("p1552.out","w",stdout);
cin >> n;
dfs(n, 1, 0);
fclose(stdin);
fclose(stdout);
return 0;
}
( )
|
| ff |
#include <iostream>
using namespace std;
const int MAX_N = 1005;
char maze[MAX_N][MAX_N];
int visited[MAX_N][MAX_N];
int component_size[MAX_N * MAX_N];
int component_id = 0;
int n, m;
int queue_x[MAX_N * MAX_N];
int queue_y[MAX_N * MAX_N];
int front, rear;
void push(int x, int y) {
queue_x[rear] = x;
queue_y[rear] = y;
rear++;
}
void pop() {
front++;
}
int getFrontX() {
return queue_x[front];
}
int getFrontY() {
return queue_y[front];
}
bool empty() {
return front == rear;
}
void clearQueue() {
front = rear = 0;
}
bool isValid(int x, int y) {
return x >= 1 && x <= n && y >= 1 && y <= n;
}
void bfs(int start_x, int start_y) {
if (visited[start_x][start_y] != 0) {
return;
}
component_id++;
int count = 0;
clearQueue();
push(start_x, start_y);
visited[start_x][start_y] = component_id;
while (!empty()) {
int x = getFrontX();
int y = getFrontY();
pop();
count++;
char current = maze[x][y];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (isValid(nx, ny) && visited[nx][ny] == 0) {
if ((current == '0' && maze[nx][ny] == '1') ||
(current == '1' && maze[nx][ny] == '0')) {
visited[nx][ny] = component_id;
push(nx, ny);
}
}
}
}
component_size[component_id] = count;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> maze[i][j];
}
}for(int i = 1;i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (visited[i][j] == 0) {
bfs(i, j);
}
}
}
for (int k = 0; k < m; k++) {
int i, j;
cin >> i >> j;
cout << component_size[visited[i][j]] << "\n";
}
return 0;
}
( )
|
| ff |
#include <iostream>
using namespace std;
const int MAX_N = 1005;
char maze[MAX_N][MAX_N];
int visited[MAX_N][MAX_N];
int component_size[MAX_N * MAX_N];
int component_id = 0;
int n, m;
int queue_x[MAX_N * MAX_N];
int queue_y[MAX_N * MAX_N];
int front, rear;
void push(int x, int y) {
queue_x[rear] = x;
queue_y[rear] = y;
rear++;
}
void pop() {
front++;
}
int getFrontX() {
return queue_x[front];
}
int getFrontY() {
return queue_y[front];
}
bool empty() {
return front == rear;
}
void clearQueue() {
front = rear = 0;
}
bool isValid(int x, int y) {
return x >= 1 && x <= n && y >= 1 && y <= n;
}
void bfs(int start_x, int start_y) {
if (visited[start_x][start_y] != 0) {
return;
}
component_id++;
int count = 0;
clearQueue();
push(start_x, start_y);
visited[start_x][start_y] = component_id;
while (!empty()) {
int x = getFrontX();
int y = getFrontY();
pop();
count++;
char current = maze[x][y];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (isValid(nx, ny) && visited[nx][ny] == 0) {
if ((current == '0' && maze[nx][ny] == '1') ||
(current == '1' && maze[nx][ny] == '0')) {
visited[nx][ny] = component_id;
push(nx, ny);
}
}
}
}
component_size[component_id] = count;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> maze[i][j];
}
}for(int i = 1;i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (visited[i][j] == 0) {
bfs(i, j);
}
}
}
for (int k = 0; k < m; k++) {
int i, j;
cin >> i >> j;
cout << component_size[visited[i][j]] << "\n";
}
return 0;
}
( )
|
|
|
|
|
|
|
|
|
|
Flag |
|
题号 |
P1608 |
|
其它 |
通过 |
32人 |
提交 |
82次 |
通过率 |
39% |
难度 |
0 |
|
|
|
|
|
|
