GALA

1086

L._16
AC不了怎么办
Yun_Daidai
CS10086

BILL01

Skuy

scx

Femnop

GALA
8小时前

# [USACO10OCT]Lake Counting S

## 题目描述

Due to recent rains, water has pooled in various places in Farmer John’s field, which is represented by a rectangle of N x M (1 <= N <= 100; 1 <= M <= 100) squares. Each square contains either water (‘W’) or dry land (‘.’). Farmer John would like to figure out how many ponds have formed in his field. A pond is a connected set of squares with water in them, where a square is considered adjacent to all eight of its neighbors. Given a diagram of Farmer John’s field, determine how many ponds he has.

## 输入格式

Line 1: Two space-separated integers: N and M * Lines 2..N+1: M characters per line representing one row of Farmer John’s field. Each character is either ‘W’ or ‘.’. The characters do not have spaces between them.

## 输出格式

Line 1: The number of ponds in Farmer John’s field.

10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

3

## 提示

OUTPUT DETAILS: There are three ponds: one in the upper left, one in the lower left, and one along the right side.

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 110;

int n, m;
char g[N][N];
bool st[N][N]; //存状态：淹没淹过
int res = 0;

int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};

void dfs(int x, int y){
for(int i = 0; i < 8; i++){
int a = x + dx[i], b = y + dy[i];

if(a < 0 || a >= n || b < 0 || b >= m) continue;
if(g[a][b] != 'W') continue;
if(st[a][b]) continue;

st[a][b] = true;
dfs(a, b);
}
}

int main()
{
scanf("%d %d", &n, &m);
for(int i = 0; i < n; i++){
scanf("%s", g[i]);
}

for(int i = 0; i < n; i++){
for(int j = 0; j< m; j++){
if(g[i][j] == 'W' && !st[i][j]){
dfs(i, j);
res++;
}
}
}
printf("%d\n", res);
return 0;
}

GALA
20小时前

# 入门

11 9
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#.......#.
.#########.
...........

59

## 提示

#### 数据规模与约定

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 30;

int n, m;  //n行m列
char g[N][N];
int res = 0;  //记录走过的瓷砖数
bool st[N][N];  //记录每块瓷砖 走过或者没走过

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

//当前访问到的坐标（x， y）
void dfs(int x, int y){
for(int i = 0; i < 4; i++){
int a = x + dx[i], b = y + dy[i];

if(a < 0 || a >= n || b < 0 || b >= m) continue;
if(g[a][b] != '.') continue;
if(st[a][b]) continue;

//走（a， b）这个点
st[a][b] = true;
res++;
dfs(a, b);
}
}

int main()
{
scanf("%d %d", &m, &n);
for(int i = 0; i < n; i++){
scanf("%s", g[i]);
}

for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(g[i][j] == '@'){
st[i][j] = true;
dfs(i, j);
}
}
}
res++;
printf("%d\n", res);
return 0;
}

GALA
20小时前

# 八数码难题

283104765

4

## 提示

### 样例解释

#include<iostream>
#include<algorithm>
#include<cstring>
#include<unordered_map>
#include <queue>
#include<string>

using namespace std;

const int N = 10;

string s;
queue<string> q;
unordered_map<string, int> dist;
unordered_map<string, int> vis;  //哈希表来存每个状态的标记--> 1 或 2
string end1 = "123804765";

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int bfs(string s)
{
dist[end1] = 0;
q.push(s), q.front();
vis[s] = 1, vis[end1] = 2;

while(q.size()){
auto t = q.front();
q.pop();

int distance  = dist[t];  //记录队头到起点的距离
int flag = vis[t];  //存队头的标记

int x = t.find('0');  //找到‘0’ 的位置
int xx = x / 3, xy = x % 3;  //一维——> 二维

//只有二维坐标才可以去遍历四个方向
for(int i = 0; i < 4; i++){
int a = xx + dx[i], b = xy + dy[i];

if(a < 0 || a >= 3 || b < 0 || b >= 3) continue;

int tmp = a * 3 + b;  //二维坐标再转换回一位坐标
swap(t[x], t[tmp]);

//此时的t是下一个状态的t：队头拓展出来的点的状态
if(vis[t] + flag == 3){  //如果队头的标记 和 对头拓展出来的点的标记 相加 为3，（1+2），就说明两个标记重合，到此，搜索结束
int res1 = dist[t];  //存拓展出来的点 距离起点的位置
swap(t[x], t[tmp]);  //再交换回来，此时的t就是取出的队头了！
int res2 = dist[t];  //再用res2 存一下队头的距离
return res1 + res2 + 1;
}

if(!dist.count(t)){
dist[t] = distance + 1;
vis[t] = flag;  //拓展出来的点 的 标记 要 跟随 队头的标记
q.push(t);
}

swap(t[x], t[tmp]);  //恢复现场
}
}
return -1;
}

int main()
{
cin >> s;  //start
if(s == end1){
printf("0\n");
return 0;
}
int res = bfs(s);
//printf("%d\n", res);
cout << res << endl;
return 0;
}

GALA
21小时前

# 离开中山路

## 题目背景

《爱与愁的故事第三弹·shopping》最终章。

3
001
101
100
1 1 3 3

4

## 提示

#include<iostream>
#include<algorithm>
#include<cstring>

#define x first
#define y second

using namespace std;
typedef pair<int, int> PII;

const int N = 1100;

int n;
char g[N][N];
int dist[N][N];
int vis[N][N];
PII q[N * N];
int x1, y1, x2, y2;

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int bfs()
{
memset(dist, -1, sizeof dist);
memset(vis, -1, sizeof vis);

dist[x1][y1] = 0, dist[x2][y2] = 0;
vis[x1][y1] = 1, vis[x2][y2] = 2;
q[0] = {x1, y1}, q[1] = {x2, y2};
int hh = 0, tt = 1;

while(hh <= tt){
auto t = q[hh++];

for(int i = 0; i < 4; i++){
int a = t.x + dx[i], b = t.y + dy[i];

if(a < 1 || a > n || b < 1 || b > n) continue;
if(g[a][b] != '0') continue;

if(vis[a][b] + vis[t.x][t.y] == 3){
return dist[t.x][t.y] + dist[a][b] + 1;
}
if(dist[a][b] >= 0) continue;

dist[a][b] = dist[t.x][t.y] + 1;
if(vis[a][b] == -1) vis[a][b] = vis[t.x][t.y];

q[++tt] = {a, b};
}
}
return -1;
}

int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%d", g[i] + 1);
}

scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
int res = bfs();
printf("%d\n", res);
return 0;
}
//不知道为什么AC不了

GALA
1天前

# 八数码难题

283104765

4

## 提示

### 样例解释

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include <queue>
#include<unordered_map>

using namespace std;

string end0 = "123804765";
unordered_map<string, int> dist;  //dist记录走到string这个状态需要走多少步
queue<string> q;

int dx[]  = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

int bfs(string start)
{
dist[start] = 0;
q.push(start);

while(q.size()){
auto t = q.front();
q.pop();

if(t == end0){
return dist[t];
}

int distance = dist[t];

int a = t.find('0'); //找到字符0的位置（即下标）
int x1 = a / 3, y1 = a % 3;  //一维数组下标转换为二维数组下标（将字符串3*3矩阵--把字符0在3*3中的坐标算出来

for(int i = 0; i < 4; i++){
int x2 = x1 + dx[i], y2 = y1 + dy[i];

if(x2 < 0 || x2 >= 3 || y2 < 0 || y2 >= 3) continue;

int tmp = x2 * 3 + y2;  //将3*3矩阵坐标转换为一位字符串的坐标
swap(t[a], t[tmp]);  //在字符串中将这两个位置互换

//如果下个位置没被访问过的话--进入循环
if(!dist.count(t)){  //count函数（map里的函数）-->例如：count(1)-->看map里有没有key值为1的元素，如果有则返回1，否则返回0；
dist[t] = distance + 1;
q.push(t);
}

swap(t[a], t[tmp]);  //恢复现场，给下个方向做准备
}
}
return -1;
}

int main()
{
string start;
cin >> start;

int res = bfs(start);
printf("%d\n", res);
return 0;
}

//哈希表--map 或 unoredered_map

GALA
2天前

# 小明的游戏

2 2
@#
#@
0 0 1 1
2 2
@@
@#
0 1 1 0
0 0

2
0

## 提示

//《deque》 队列的头既有进队列的也有出队列的，队列的尾既有进队列的也有出队列的--即双端
#include<iostream>
#include<algorithm>
#include<cstring>
#include<deque>

#define fi first
#define sc second

using namespace std;

const int N = 510;
typedef pair<int, int> PII;

int n, m;
char g[N][N];
int x1, x2, y1, y2;
deque<PII> q;
int dist[N][N];

int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

int bfs(int x, int y){
q.push_back({x, y});
dist[x][y] = 0;

while(q.size()){
auto t = q.front();
q.pop_front();
//printf("t = (%d %d)\n", t.fi, t.sc);
char ch = g[t.fi][t.sc];

for(int i = 0; i < 4; i++){
int a = t.fi + dx[i], b = t.sc + dy[i];

if(a < 0 || a >= n || b < 0 || b >= m) continue;
if(dist[a][b] >=  ch) continue;

if(g[a][b] == ch){
dist[a][b] = dist[t.fi][t.sc];
q.push_front({a, b});
}

if(g[a][b] != ch){
dist[a][b] = dist[t.fi][t.sc] + 1;
q.push_back({a, b});
}

if(a == x2 && b == y2) return dist[x2][y2];
}
}
return -1;
}

int main()
{
while(cin >> n >> m, n || m){
for(int i = 0; i < n; i++){
scanf("%s", g[i]);
}
memset(dist, -1, sizeof dist);
q.clear();
cin >> x1 >> y1 >> x2 >> y2;
int res = bfs(x1, y1);
cout << res << endl;
}
return 0;
}

//《deque》 队列的头既有进队列的也有出队列的，队列的尾既有进队列的也有出队列的--即双端

GALA
3天前

A=[A1,A2,…AN]
,
B=[B1,B2,…BN]
,
C=[C1,C2,…CN]
,

1≤i,j,k≤N
Ai<Bj<Ck

1≤N≤105
,
0≤Ai,Bi,Ci≤105

3
1 1 1
2 2 2
3 3 3

27

//二分（之前提交的）
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 100010;

int n;
int a[N], b[N], c[N];

//在A中找到最后一个小于B的数的位置
//在C中找到第一个大于B的数的位置
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
for(int i = 1; i <= n; i++) scanf("%d", &b[i]);
for(int i = 1; i <= n; i++) scanf("%d", &c[i]);

sort(a + 1, a + 1 + n);
sort(b + 1, b + 1 + n);
sort(c + 1, c + 1 + n);

long long res = 0;  //long long --最坏情况下要用long long
for(int i = 1, IndexA = 1, IndexC = 1; i <= n; i++){  //IndexA--指针 IndexC同理
int B = b[i];
while(IndexA <= n && a[IndexA] < B){  //在A中找到最后一个小于B的数的位置
IndexA++;
}
while(IndexC <= n && c[IndexC] <= B){  //在C中找到第一个大于B的数的位置
IndexC++;
}
res += (long long)(IndexA - 1) * (n - IndexC + 1);   //强转成long long
}
printf("%lld\n", res);
return 0;
}

GALA
7天前

# A-B 数对

4 1
1 1 2 3

3

## 提示

2017/4/29 新添数据两组

//b指针中又分了两个指针—-b1和b2
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 200010;

int n, C;
int q[N];

int main()
{
scanf("%d %d", &n, &C);
for(int i = 1; i <= n; i++){
scanf("%d", &q[i]);
}

sort(q + 1, q + 1 + n);

long long res = 0;
for(int a = 1, b1 = 1, b2 = 1; a <= n; a++){
while(b1 <= a && q[a] - q[b1] >= C){
b1++;
}
while(b2 <= a && q[a] - q[b2] > C){
b2++;
}
res += b1 - b2;
}

printf("%lld\n", res);
return 0;
}

GALA
7天前

5

1 ≤ 1≤1≤ 数组元素 ≤ 1 0 9 ≤10^9≤10
9

4 5 6
1 2 4 7
3 4 6 8 9
1
2
3

1 1
————————————————

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 100010;

int n, m, x;
int a[N], b[N];

int main()
{
scanf("%d %d %d", &n, &m, &x);
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
}
for(int i = 1; i <= n; i++){
scanf("%d", &b[i]);
}

for(int i = 1, j = m; i <= n; i++){
while(j >= 1 && a[i] + b[j] > x){
j--;
}
if(a[i] + b[j] == x){
printf("%d %d\n", i - 1, j - 1);
return 0;
}
}
return 0;
}

GALA
8天前

，表示一个子矩阵的左上角坐标和右下角坐标。

，表示一组询问。

1≤n,m≤1000
,
1≤q≤200000
,
1≤x1≤x2≤n
,
1≤y1≤y2≤m
,
−1000≤矩阵内元素的值≤1000

3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4

17
27
21

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m, k;
int q[N][N];
int s[N][N];  //前缀和数组的和

int main()
{
cin >> n >> m >> k;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
scanf("%d", &q[i][j]);
s[i][j] = q[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
}
}
while(k--){
int x1, x2, y1, y2;
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
printf("%d\n", s[x2][y2] - s[x2][y1 -1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]);
//**printf("%d\n", s[x2][y2] - s[x2][y1 -1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]);**
}
return 0;
}