今天大家一起做的div2，怎麼說呢，前三題有點坑，好多特判....
A. Cakeminator
題目的意思是說，讓你吃掉cake,並且是一行或者一列下去，但是必須沒有草莓的存在。這道題目，就是判斷一下每行和每列的情況，看是不是有草莓存在，有的話就標記一下。後面就直接把木有草莓的行和列求和再減去重復路過的cake就行，不過你第一遍寫的比較麻煩，小數據過了，後來WA了，現在改了一種寫法。就是簡單的加加減減。上代碼：
[cpp]
<SPAN style="FONT-FAMILY: KaiTi_GB2312; FONT-SIZE: 18px">#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <map>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
using namespace std;
int n, m;
char sp[200][200];
int x[200];
int y[200];
int main()
{
scanf("%d%d", &n, &m);
for(int i = 0; i< n; ++i)
scanf("%s", sp[i]);
memset(x, 0, sizeof(x));
memset(y, 0, sizeof(y));
int sumxs = 0, sumys = 0;
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < m; ++j)
{
if(sp[i][j] == 'S')
{
x[i] = 1;
sumxs++;
break;
}
}
}
for(int i = 0; i < m; ++i)
for(int j = 0; j <n; ++j)
{
if(sp[j][i] == 'S')
{
y[j] =1;
sumys++;
break;
}
}
//cout << sumxs << ' ' << sumys <<endl;
int cnt = 0;
cnt += (n-sumxs)*m;
cnt += (m-sumys)*n;
//cout << cnt <<endl;
cnt -= ((n-sumxs)*(m-sumys));
cout << cnt <<endl;
return 0;
}</SPAN>
#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <map>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
using namespace std;
int n, m;
char sp[200][200];
int x[200];
int y[200];
int main()
{
scanf("%d%d", &n, &m);
for(int i = 0; i< n; ++i)
scanf("%s", sp[i]);
memset(x, 0, sizeof(x));
memset(y, 0, sizeof(y));
int sumxs = 0, sumys = 0;
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < m; ++j)
{
if(sp[i][j] == 'S')
{
x[i] = 1;
sumxs++;
break;
}
}
}
for(int i = 0; i < m; ++i)
for(int j = 0; j <n; ++j)
{
if(sp[j][i] == 'S')
{
y[j] =1;
sumys++;
break;
}
}
//cout << sumxs << ' ' << sumys <<endl;
int cnt = 0;
cnt += (n-sumxs)*m;
cnt += (m-sumys)*n;
//cout << cnt <<endl;
cnt -= ((n-sumxs)*(m-sumys));
cout << cnt <<endl;
return 0;
}
B. Road Construction
題目的意思是說現在給你n個點，然後在給你m個關系，這m個個關系表示某兩條邊之間不能連邊，問你求最短的建築方案是什麼，要求任意兩點之間距離不能超過2.
這道題目當時糾結了很久，不知道怎麼去鏈接，後面才想到這只能是所有的點圍在一個點的周圍的情況。其它的總會有兩點之間的距離超過2的。所以就簡單了，直接找到可以和任何一個點相連的點，輸出他和剩下的點的序列就行了 。
[cpp]
<SPAN style="FONT-FAMILY: KaiTi_GB2312; FONT-SIZE: 18px">#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <map>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
using namespace std;
char sp[200][200];
int main()
{
int n;
scanf("%d", &n);
for(int i = 0; i < n; ++i)
scanf("%s", sp[i]);
int hang = 0;
int sum[10000];
int k = 0;
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < n; ++j)
{
if(sp[i][j] == '.')
{
//cout << i << ' ' << j <<endl;
hang++;
sum[k++] = i+1;
sum[k++] = j+1;
break;
}
}
}
if(hang == n)
{
for(int i = 0; i < k-1; i+=2)
printf("%d %d\n", sum[i], sum[i+1]);
}
else
{
int lie = 0;
k = 0;
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < n; ++j)
{
if(sp[j][i] == '.')
{
//cout << i << ' ' << j <<endl;
lie++;
sum[k++] = j+1;
sum[k++] = i+1;
break;
}
}
}
if(lie < n)
printf("-1\n");
else
{
for(int i = 0; i < k-1; i+=2)
printf("%d %d\n", sum[i], sum[i+1]);
}
}
return 0;
}</SPAN>
#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <map>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
using namespace std;
char sp[200][200];
int main()
{
int n;
scanf("%d", &n);
for(int i = 0; i < n; ++i)
scanf("%s", sp[i]);
int hang = 0;
int sum[10000];
int k = 0;
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < n; ++j)
{
if(sp[i][j] == '.')
{
//cout << i << ' ' << j <<endl;
hang++;
sum[k++] = i+1;
sum[k++] = j+1;
break;
}
}
}
if(hang == n)
{
for(int i = 0; i < k-1; i+=2)
printf("%d %d\n", sum[i], sum[i+1]);
}
else
{
int lie = 0;
k = 0;
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < n; ++j)
{
if(sp[j][i] == '.')
{
//cout << i << ' ' << j <<endl;
lie++;
sum[k++] = j+1;
sum[k++] = i+1;
break;
}
}
}
if(lie < n)
printf("-1\n");
else
{
for(int i = 0; i < k-1; i+=2)
printf("%d %d\n", sum[i], sum[i+1]);
}
}
return 0;
}
C. Purification
題目的意思是說，你面對一個方格，這個方格的，每一個點都需要“清洗”一下。但是有的點是可以站立的，有些點是僵屍，不能站立。你的能力是當你站在一個點上時，你可以“清洗”你所在的行和列。現在給你當前方格的狀態，求出最小的站立點數，使得所有的點都能被“清洗”掉。
就是把每一行和每一列“覆蓋”一下啊。站就行了。從行開始檢測，如果每一行都可以站立，那就OK了。不能的話就在從列開始檢測，如果可以就OK，還是不行的話就輸出“-1”就可以了。最少的步數不是行數/列數就是-1了，OK，判斷：
[cpp]
<SPAN style="FONT-FAMILY: KaiTi_GB2312; FONT-SIZE: 18px">#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <map>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
using namespace std;
char sp[200][200];
int main()
{
int n;
scanf("%d", &n);
for(int i = 0; i < n; ++i)
scanf("%s", sp[i]);
int hang = 0;
int sum[10000];
int k = 0;
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < n; ++j)
{
if(sp[i][j] == '.')
{
//cout << i << ' ' << j <<endl;
hang++;
sum[k++] = i+1;
sum[k++] = j+1;
break;
}
}
}
if(hang == n)
{
for(int i = 0; i < k-1; i+=2)
printf("%d %d\n", sum[i], sum[i+1]);
}
else
{
int lie = 0;
k = 0;
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < n; ++j)
{
if(sp[j][i] == '.')
{
//cout << i << ' ' << j <<endl;
lie++;
sum[k++] = j+1;
sum[k++] = i+1;
break;
}
}
}
if(lie < n)
printf("-1\n");
else
{
for(int i = 0; i < k-1; i+=2)
printf("%d %d\n", sum[i], sum[i+1]);
}
}
return 0;
}</SPAN>
#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <map>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
using namespace std;
char sp[200][200];
int main()
{
int n;
scanf("%d", &n);
for(int i = 0; i < n; ++i)
scanf("%s", sp[i]);
int hang = 0;
int sum[10000];
int k = 0;
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < n; ++j)
{
if(sp[i][j] == '.')
{
//cout << i << ' ' << j <<endl;
hang++;
sum[k++] = i+1;
sum[k++] = j+1;
break;
}
}
}
if(hang == n)
{
for(int i = 0; i < k-1; i+=2)
printf("%d %d\n", sum[i], sum[i+1]);
}
else
{
int lie = 0;
k = 0;
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < n; ++j)
{
if(sp[j][i] == '.')
{
//cout << i << ' ' << j <<endl;
lie++;
sum[k++] = j+1;
sum[k++] = i+1;
break;
}
}
}
if(lie < n)
printf("-1\n");
else
{
for(int i = 0; i < k-1; i+=2)
printf("%d %d\n", sum[i], sum[i+1]);
}
}
return 0;
}
D. Biridian Forest
題目的意思就是打怪，你站在S點，要前往E點，但是森林中存在怪物，他們也會移動，並且移動的速度和你的一樣。你如果到達一個點，這個點也有怪物的話，那你就需要大戰怪獸，大戰的次數等於怪物的數量。問你最少的大戰次數是多少。
由於要求最優路徑，肯定要用到BFS，再者，我們需要考慮如何計算我們會不會和怪獸碰上。按照題目意思，只要我們到出口的距離大於怪獸的點到出口的距離，那麼我們就會碰到怪獸，這樣的話，就直接可以從出口開始，求出各個點到出口的最短距離，再把怪獸的距離和我們的S的距離進行比較，如果小於的話那就不可避免的大戰了，額，好吧。就是這樣了：
[cpp]
#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <map>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
using namespace std;
char sp[1500][1500];
struct node
{
int x;
int y;
} st,ed;
int vis[1500][1500];
int n, m;
int dx[4] = {0, 0, -1, 1};
int dy[5] = {-1, 1, 0, 0};
bool inmap(node a)
{
if(a.x <0||a.x >= n || a.y<0 || a.y >=m)
return false;
return true;
}
void BFS()
{
memset(vis, -1, sizeof(vis));
queue<node>Q;
vis[ed.x][ed.y] = 0;
Q.push(ed);
node next;
while(!Q.empty())
{
node tp = Q.front();
Q.pop();
for(int i = 0; i < 4; ++i)
{
next.x = tp.x+dx[i];
next.y = tp.y+dy[i];
if(inmap(next) && vis[next.x][next.y]==-1&&sp[next.x][next.y]!='T')
{
vis[next.x][next.y] = vis[tp.x][tp.y]+1;
Q.push(next);
}
}
}
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 0; i < n; ++i)
scanf("%s", sp[i]);
int flag = 0;
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < m; ++j)
{
if(sp[i][j] == 'S')
{
st.x = i;
st.y = j;
if(flag == 1)
{
i = n;
j = m;
}
else
flag = 1;
}
if(sp[i][j] == 'E')
{
ed.x = i;
ed.y = j;
if(flag == 1)
{
i = n;
j = m;
}
else
flag = 1;
}
}
}
BFS();
int cnt = 0;
int MAX = vis[st.x][st.y];
for(int i = 0; i <n ; ++i)
{
for(int j = 0; j < m; ++j)
{
if(sp[i][j]>='1'&& sp[i][j]<='9')
if(vis[i][j] <= MAX && vis[i][j] != -1)
cnt+=(sp[i][j] - '0');
}
}
cout << cnt <<endl;
return 0;
}
#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <map>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
using namespace std;
char sp[1500][1500];
struct node
{
int x;
int y;
} st,ed;
int vis[1500][1500];
int n, m;
int dx[4] = {0, 0, -1, 1};
int dy[5] = {-1, 1, 0, 0};
bool inmap(node a)
{
if(a.x <0||a.x >= n || a.y<0 || a.y >=m)
return false;
return true;
}
void BFS()
{
memset(vis, -1, sizeof(vis));
queue<node>Q;
vis[ed.x][ed.y] = 0;
Q.push(ed);
node next;
while(!Q.empty())
{
node tp = Q.front();
Q.pop();
for(int i = 0; i < 4; ++i)
{
next.x = tp.x+dx[i];
next.y = tp.y+dy[i];
if(inmap(next) && vis[next.x][next.y]==-1&&sp[next.x][next.y]!='T')
{
vis[next.x][next.y] = vis[tp.x][tp.y]+1;
Q.push(next);
}
}
}
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 0; i < n; ++i)
scanf("%s", sp[i]);
int flag = 0;
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < m; ++j)
{
if(sp[i][j] == 'S')
{
st.x = i;
st.y = j;
if(flag == 1)
{
i = n;
j = m;
}
else
flag = 1;
}
if(sp[i][j] == 'E')
{
ed.x = i;
ed.y = j;
if(flag == 1)
{
i = n;
j = m;
}
else
flag = 1;
}
}
}
BFS();
int cnt = 0;
int MAX = vis[st.x][st.y];
for(int i = 0; i <n ; ++i)
{
for(int j = 0; j < m; ++j)
{
if(sp[i][j]>='1'&& sp[i][j]<='9')
if(vis[i][j] <= MAX && vis[i][j] != -1)
cnt+=(sp[i][j] - '0');
}
}
cout << cnt <<endl;
return 0;
}
