Crossword Answers

Samples
Input 复制
2 2
AT
O
6 7
AIMDEN
MEONE
UPONTO
SOERIN
SAOR*
IES*DEA
0
Output
puzzle #1:
Across
1.AT
3.O
Down
1.A
2.TO

puzzle #2:
Across
1.AIM
4.DEN
7.ME
8.ONE
9.UPON
11.TO
12.SO
13.ERIN
15.SA
17.OR
18.IES
19.DEA
Down
1.A
2.IMPOSE
3.MEO
4.DO
5.ENTIRE
6.NEON
9.US
10.NE
14.ROD
16.AS
18.I
20.A
Source
UVA 232

题意：
一个二维矩阵
黑色的用 * 表示
白色的填入字母
如果目前这个是个白色的 然后上面或者左边也是白色的 或者左边或者上边是边界
那么他就会被赋予一个编号 一行一行的 从1开始
然后先按行输出 被 * 分开的单词 输出每个单词的首位编号
然后按列输出
注意编号从小到大输出
这题 唉 无语

#include<bits/stdc++.h>
#include<iostream>
#include<cstring>
#include<queue>
#define inf 0x3f3f3f3f
//2147483647
using namespace std;
typedef long long ll;
typedef pair<int, string> PII;
ll n,m,k,T;
ll cnt=0,ans=0;
ll mod=1e9+7;
const int maxn=2e5+199;
ll a[maxn];ll dp[500][500];
string s[maxn];
priority_queue< PII,vector<PII>,greater<PII> >q;
int main(){
    while(scanf("%lld",&n)!=EOF){
    if(n==0)break;cin>>m;for(int i=0;i<n;i++){
    cin>>s[i];}cnt=0;for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
    if((i==0||j==0)||(s[i-1][j]=='*'||s[i][j-1]=='*')){
    if(s[i][j]!='*')dp[i][j]=++cnt;}}}int i=0;cout<<"puzzle #"<<++ans<<":"<<endl;cout<<"Across"<<endl;for(i;i<n;i++){
    int j=0;for(j;j<m;j++){
    if(s[i][j]!='*'){
    printf("%3lld.",dp[i][j]);while(s[i][j]!='*'&&j<m){
    cout<<s[i][j];j++;}cout<<endl;}}}i=0;cout<<"Down"<<endl;int dj=0;for(i;i<m;i++){
     //把每一列分的单词存起来 顺便把编号存起来 输出的时候直接first排序 多省事int j=0;for(j;j<n;j++){
    if(s[j][i]!='*'){
    string ss="";int op=dp[j][i];while(s[j][i]!='*'&&j<n){
    ss+=s[j][i];j++;}q.push(make_pair(op,ss)); }}}while(q.size()){
    PII f=q.top();printf("%3d",int(f.first));cout<<'.'<<f.second<<endl;q.pop();}cout<<endl;}return 0;
}