Uva101,此题三种代码,答案不同,却都能AC通过
查看原帖
Uva101,此题三种代码,答案不同,却都能AC通过
376953
冬日暖陽楼主2020/9/3 22:02

真是发现个有趣(奔溃)的现象。我们来看以下三种题解代码(注明:参考代码。来源于CSDN和本题的解析) 先看第一类

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int A[30][30],x,y,z,w;
char s1[10],s2[10];
int a,b,op,n;
void Find(int c,int &u,int &v){
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
        if(A[i][j]==c){ u=i;v=j;}
}
bool islegal(){
    if(a==b)return 0;
    Find(a,x,y);
    Find(b,z,w);
    if(x==z)return 0;
    return 1;
}
void restore(int p){
    Find(p,x,y);
    while(A[x][++y]!=-1){
        int t= A[x][y];
        A[t][0]=t;
        A[x][y]=-1;
    }
}
void pile(int a,int b){
    Find(a,x,y);
    Find(b,z,w);
    while(A[z][++w]!=-1);w--;
    while(A[x][y]!=-1){
        A[z][++w]=A[x][y];
        A[x][y++]=-1;
    }
}
int main(){
    //freopen("1.in","r",stdin);
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)A[i][j]=-1;
        A[i][0]=i;
    }
    while(scanf("%s",s1)!=EOF && s1[0]!='q'){
        scanf("%d%s%d",&a,s2,&b);
        if(islegal()==0)continue;
        if(s1[0]=='m')restore(a);
        if(s2[1]=='n')restore(b);
        pile(a,b);
    }
    for(int i=0;i<n;i++){
        printf("%d:",i);
        int k=0;
        while(A[i][k]!=-1)
            printf(" %d",A[i][k++]);
        printf("\n");
    }
}

这段来源于解析,当我们测试同一个测试用例时,如下 7

move 6 over 5

pile 3 on 0

pile 5 on 1

move 2 on 0

pile 0 on 1

move 0 over 2

move 1 over 1

move 5 over 3

pile 6 over 5

pile 3 over 1

quit 此时的答案是 0: 1: 1 3 5 6 2: 2 0 3: 4: 4 5: 6: 代码可以AC通过

再看下面第二类代码

#include<cstdio>
#include<string>
#include<vector>
#include<iostream>
using namespace std;
const int maxn = 30;
int n;
vector<int> pile[maxn];
//找木块a所在的pile 和height, 以引用的形式返回调用者
void find_block(int a , int & p , int & h)
{
    for(p = 0 ; p < n ;p++)
        for( h = 0 ; h < pile[p].size() ; h++)
            if(pile[p][h]==a) return;
}
//把第p堆高度为h的木块上方的所有木块移回原位
void clear_above(int p , int h )
{
    for(int i = h+1; i < pile[p].size(); i++)
    {
        int b = pile[p][i];
        pile[b].push_back(b);//把木块b放回原位
    }
    pile[p].resize(h+1);//pile只保留下标为0~h的元素
}
//把第p堆高度为h及其上方的木块整体移动到p2堆的顶部
void pile_onto(int p , int h , int p2)
{
    for(int i = h ; i < pile[p].size() ; i++)
    pile[p2].push_back(pile[p][i]);
    pile[p].resize(h);
}
void print()
{
    for(int i = 0 ; i < n ;i++)
    {
        printf("%d:",i);
        for(int j = 0 ;j < pile[i].size();j++) printf(" %d",pile[i][j]);
        printf("\n");
    }
}
int main()
{
    int a , b;
    cin>>n;
    string s1 , s2;
    for(int i = 0 ; i < n ;i++) pile[i].push_back(i);
    while(cin>>s1>>a>>s2>>b)
    {
        int pa , pb , ha, hb ;
        find_block(a,pa,ha);
        find_block(b,pb,hb);
        if(pa==pb) continue;//非法指令
        if(s2=="onto") clear_above(pb,hb);
        if(s1=="move") clear_above(pa,ha);
        pile_onto(pa,ha,pb);
    }
    print();
    return 0;
}

此时输入同上的示例,答案是 0: 1: 1 5 6 0 3 2 2: 3: 4: 4 5: 6:

在看第三类代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int A[30][30],x,y,z,w;
char s1[10],s2[10];
int a,b,op,n;
void Find(int c,int &u,int &v){
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
        if(A[i][j]==c){ u=i;v=j;}
}
bool islegal(){
    if(a==b)return 0;
    Find(a,x,y);
    Find(b,z,w);
    if(x==z)return 0;
    return 1;
}
void restore(int p){
    Find(p,x,y);
    while(A[x][++y]!=-1){
        int t= A[x][y];
        A[t][0]=t;
        A[x][y]=-1;
    }
}
void pile(int a,int b){
    Find(a,x,y);
    Find(b,z,w);
    while(A[z][++w]!=-1);w--;
    while(A[x][y]!=-1){
        A[z][++w]=A[x][y];
        A[x][y++]=-1;
    }
}
int main(){
    //freopen("1.in","r",stdin);
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)A[i][j]=-1;
        A[i][0]=i;
    }
    while(scanf("%s",s1)!=EOF && s1[0]!='q'){
        scanf("%d%s%d",&a,s2,&b);
        if(islegal()==0)continue;
        if(s1[0]=='m')restore(a);
        if(s2[1]=='n')restore(b);
        pile(a,b);
    }
    for(int i=0;i<n;i++){
        printf("%d:",i);
        int k=0;
        while(A[i][k]!=-1)
            printf(" %d",A[i][k++]);
        printf("\n");
    }
}

同样是AC,此时输入同第一个的示例,答案却是 0: 1: 1 0 2 3 5 6 2: 3: 4: 4 5: 6:

我就很奔溃,为什么会这样呢? 最后我附上我的通不过的代码

#include <iostream>
#include <vector>
#include <iomanip>
#include <string>
#include <sstream>
#include <stack>
#include <utility>

using namespace std;

//输出vector
/*  不Accept
std::ostream& operator<<(std::ostream& out, vector<vector<int> >& vect)							//为vector重载<<运算符
{
    int i = 0;
    for (vector<vector<int> >::iterator iter = vect.begin(); iter != vect.end(); iter++)	//通过迭代器遍历所有元素,等价于for_each()
    {
        out << i << ":";
        for (int i = 0; i < iter->size(); i++) {
            out <<" "<<(*iter)[i];
        }
        i++;
        out << endl;
    }
    return out;
}
*/

void print(vector<vector<int> >& vect) {
    int i = 0;
    for (vector<vector<int> >::iterator iter = vect.begin(); iter != vect.end(); iter++)	//通过迭代器遍历所有元素,等价于for_each()
    {
        cout << i << ":";
        for (int i = 0; i < iter->size(); i++) {
            cout << " " << (*iter)[i];
        }
        i++;
        cout << endl;
    }
}

//物理模型地址模拟方法
pair<int, int> search(vector<vector<int> >& vect, int number) {     //寻找该数所在的坐标(列,高)
    for (int i = 0; i < vect.size(); i++) {
        for (int j = 0; j < vect[i].size(); j++) {
            if (vect[i][j] == number) {
                return make_pair(i, j);
            }
        }
    }
}
//---------------vector个数守恒原则:push_back()和pop_back()对应。
void reset(vector<vector<int> >& vect, int x, int y) {       //复位(x,y)位置之上的木块
    int number;
    if (vect[x].size() >= y + 1) {
        for (int i = 0; i < vect[x].size() - y - 1; /*i++*/) {      //-y-1不包括本身,-y包括本身。
            number = vect[x].back();
            vect[number].push_back(number);
            vect[x].pop_back();
        }
    }
}

stack<int> preserve(vector<vector<int> >& vect, int x, int y) {      //暂存(x,y)位置之上的木块
    stack<int> st;
    int number;
    if (vect[x].size() >= y + 1) {
        for (int i = 0; i < vect[x].size() - y; /*i++*/) {      //暂存于堆栈,每执行一次vect[x].size()的大小会减1。
            number = vect[x].back();
            st.push(number);
            vect[x].pop_back();
        }
    }
    return st;
}

void moveonto(vector<vector<int> >& vect, int a, int b) {
    int x1, x2, y1, y2;
    pair<int, int> p;
    p = search(vect, a);
    x1 = p.first;
    y1 = p.second;
    p = search(vect, b);
    x2 = p.first;
    y2 = p.second;
    reset(vect, x1, y1);     //a的上方归位
    reset(vect, x2, y2);     //b的上方归位
    vect[x2].push_back(vect[x1][y1]);
    vect[x1].pop_back();
}

void moveover(vector<vector<int> >& vect, int a, int b) {
    int x1, x2, y1, y2;
    pair<int, int> p;
    p = search(vect, a);
    x1 = p.first;
    y1 = p.second;
    p = search(vect, b);
    x2 = p.first;
    y2 = p.second;
    reset(vect, x1, y1);     //a的上方归位
    vect[x2].push_back(vect[x1][y1]);
    vect[x1].pop_back();
}

void pileonto(vector<vector<int> >& vect, int a, int b) {
    int x1, x2, y1, y2;
    pair<int, int> p;
    p = search(vect, a);
    x1 = p.first;
    y1 = p.second;
    p = search(vect, b);
    x2 = p.first;
    y2 = p.second;
    reset(vect, x2, y2);     //b的上方归位
    stack<int> st = preserve(vect, x1, y1);
    cout<<st.empty()<<endl;
    while (!st.empty()) {
        vect[x2].push_back(st.top());
        st.pop();
    }
    //vect[x2].push_back(vect[x1][y1]);
    //vect[x1].pop_back();
    //vect[x1][y1] = -1;
}

void pileover(vector<vector<int> >& vect, int a, int b) {
    int x1, x2, y1, y2;
    pair<int, int> p;
    p = search(vect, a);
    x1 = p.first;
    y1 = p.second;
    p = search(vect, b);
    x2 = p.first;
    y2 = p.second;
    stack<int> st = preserve(vect, x1, y1);
    while (!st.empty()) {
        vect[x2].push_back(st.top());
        st.pop();
    }
    //vect[x2].push_back(vect[x1][y1]);
    //vect[x1].pop_back();
    //vect[x1][y1] = -1;
}

int main() {
    ///步骤0 竞赛去除stdio的同步
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    ///步骤1 输入初始信息
    vector<vector<int> > vect;
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) {
        vect.push_back(vector<int>(1,i));      //空构造函数用于构建空vector;constructor(分配元素数,元素的值)
    }
    //cout << vect << endl;     //测试代码
    ///步骤2 操作木块
    //string command, buffer;
    //stringstream sstream;
    //int number;
    /// cin.get()每次读取一整行并把由Enter键生成的换行符留在输入队列中,然而cin.getline()每次读取一整行并把由Enter键生成的换行符抛弃。
    /// 这里主要针对与char类型
    /// getline()则主要针对string类库
    //cin.ignore();   //类似于cin.get(),可以忽略cin流里的回车符
    /*
    getline(cin, command, '\x1A');      //ctrl + z 结束输入

    //cout << command;
    //利用stringstream流处理字符段
    sstream << command;
    */
    string action, result;
    int start, end;

    while (!cin.eof()) {   //C语言用 scanf(...) != EOF 或者 ~scanf(...)实现多次数据输入的循环判断检查。
                           //cin则是!cin.eof()返回流结束位,即按键 ctrl+z 键
        //注意:如果a和b已经在一堆中就不要操作,此时认为不用移动,否则会WA。
        /*  答案对,但是没法Accept
        getline(cin,command);
        sstream << command;
        sstream >> action;
        if (action.compare("quit") == 0) {
            break;
        }
        sstream >> start;
        sstream >> result;
        sstream >> end;
        sstream.clear();
        */

        cin >> action;
        if (action.compare("quit") == 0) {
            break;
        }
        cin >> start >> result >> end;
        pair<int,int> same;
        same.first = search(vect, start).first;
        same.second = search(vect, end).first;
        if (same.first == same.second)       //如果木块编号一样则不操作
        {
            //cout << "此处为同一摞" << endl;
            continue;
        }
        else if (action.compare("move") == 0 && result.compare("onto") == 0) {
            if(start < N && end < N && start >= 0 && end >= 0)        //用精确的vector则必须限定好取值范围
            moveonto(vect, start, end);
        }
        else if (action.compare("move") == 0 && result.compare("over") == 0) {
            if (start < N && end < N && start >= 0 && end >= 0)
            moveover(vect, start, end);
        }
        else if (action.compare("pile") == 0 && result.compare("onto") == 0) {
            if (start < N && end < N && start >= 0 && end >= 0)
            pileonto(vect, start, end);
        }
        else if (action.compare("pile") == 0 && result.compare("over") == 0) {
            if (start < N && end < N && start >= 0 && end >= 0)
            pileover(vect, start, end);
        }
    }
    //cout << vect << endl;       //输出结果
    print(vect);
    return 0;
}

答案是 0: 1: 1 3 5 6 2: 2 0 3: 4: 4 5: 6: 但就是通不过。不知道为什么

2020/9/3 22:02
加载中...