Submission #533453

---

Source Code Expand

#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
using namespace std;

unsigned xor128(){
    static unsigned x=123456789,y=362436069,z=521288629,w=(unsigned)time(NULL);
    unsigned t;
    t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
}

int main()
{
    const int n = 10;
    const int m = 4;
    for(;;){
        vector<string> s(n, string(n, '.'));
        vector<string> t(n, string(n, '.'));
        for(int j=0; j<m; ++j){
            int y, x;
            do{
                y = xor128() % n;
                x = xor128() % n;
            }while(s[y][x] != '.');

            s[y][x] = 'C';
            for(int j=0; j<9; ++j){
                int dy = j / 3 - 1;
                int dx = j % 3 - 1;
                for(int k=1; k<=2; ++k){
                    int y2 = y + dy * k;
                    int x2 = x + dx * k;
                    if(0 <= y2 && y2 < n && 0 <= x2 && x2 < n)
                        t[y2][x2] = '#';
                }
            }
        }

        vector<vector<int> > dp(n, vector<int>(n, 0));
        for(int y=0; y<n; ++y){
            if(t[y][0] == '.')
                dp[y][0] = 1;
        }
        for(int x=1; x<n; ++x){
            for(int y=0; y<n; ++y){
                if(t[y][x] == '#')
                    continue;

                for(int i=-1; i<=1; ++i){
                    int y2 = y + i;
                    if(0 <= y2 && y2 < n)
                        dp[y][x] += dp[y2][x-1];
                }
            }
        }

        int cnt = 0;
        for(int y=0; y<n; ++y)
            cnt += dp[y][n-1];
        if(cnt == 1){
            for(int i=0; i<n; ++i)
                cout << s[i] << endl;
            return 0;
        }
    }
}

Submission Info

Judge Result