#include <iostream> #include <vector> #include <map> #include <algorithm> using namespace std; vector<map<int,int>>p; int n,m; int g(int x, int y) { auto it = p[x].find(y); if(it==p[x].end())return 0; return p[x][y]; } void s(int x, int y, int z) { if(z==0) p[x].erase(y); else p[x][y]=z; } bool trasa(int x, int y) { //printf("%d %d\n",x,y); if(x>=n)return false; if(y>=m)return false; if(g(x,y)==1) return false; if(x==n-1 && y==m-1) {s(x,y,2);return true;} if(x+1<n&& g(x+1,y)==2) { if(trasa(x+1,y)) {s(x,y,2);return true;} if(trasa(x,y+1)) {s(x,y,2);return true;} } else { if(trasa(x,y+1)) {s(x,y,2);return true;} if(trasa(x+1,y)) {s(x,y,2);return true;} } s(x,y,0); return false; } void init(unsigned int n, unsigned int m) { p = vector<map<int,int>>(n,map<int,int>()); trasa(0,0); } void clear(int x, int y) { while(!(x==n-1 && y==m-1)) { s(x,y,0); if(x+1<n && g(x+1,y)==2)x++; else y++; } s(x,y,0); } bool warownia(unsigned int x, unsigned int y) { bool r=true; if(g(x,y)==2) { clear(x,y); s(x,y,1); r=trasa(0,0); } else { s(x,y,1); } //printf("trasa: %d\n",r); if (r) printf("NIE\n"); else { printf("TAK\n"); s(x,y,0); trasa(0,0); } return r; } void rysuj() { for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { printf("%d",g(i,j)); } printf("\n"); } printf("\n"); } int main() { // your code goes here unsigned int k,x=0; scanf("%u%u%u",&n,&m,&k); init(n,m); for(int i=0;i<k;i++) { unsigned int r,c,z; scanf("%u%u%u",&r,&c,&z); if (!warownia((r^x)%n,(c^x)%m))x^=z; // rysuj(); } return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 | #include <iostream> #include <vector> #include <map> #include <algorithm> using namespace std; vector<map<int,int>>p; int n,m; int g(int x, int y) { auto it = p[x].find(y); if(it==p[x].end())return 0; return p[x][y]; } void s(int x, int y, int z) { if(z==0) p[x].erase(y); else p[x][y]=z; } bool trasa(int x, int y) { //printf("%d %d\n",x,y); if(x>=n)return false; if(y>=m)return false; if(g(x,y)==1) return false; if(x==n-1 && y==m-1) {s(x,y,2);return true;} if(x+1<n&& g(x+1,y)==2) { if(trasa(x+1,y)) {s(x,y,2);return true;} if(trasa(x,y+1)) {s(x,y,2);return true;} } else { if(trasa(x,y+1)) {s(x,y,2);return true;} if(trasa(x+1,y)) {s(x,y,2);return true;} } s(x,y,0); return false; } void init(unsigned int n, unsigned int m) { p = vector<map<int,int>>(n,map<int,int>()); trasa(0,0); } void clear(int x, int y) { while(!(x==n-1 && y==m-1)) { s(x,y,0); if(x+1<n && g(x+1,y)==2)x++; else y++; } s(x,y,0); } bool warownia(unsigned int x, unsigned int y) { bool r=true; if(g(x,y)==2) { clear(x,y); s(x,y,1); r=trasa(0,0); } else { s(x,y,1); } //printf("trasa: %d\n",r); if (r) printf("NIE\n"); else { printf("TAK\n"); s(x,y,0); trasa(0,0); } return r; } void rysuj() { for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { printf("%d",g(i,j)); } printf("\n"); } printf("\n"); } int main() { // your code goes here unsigned int k,x=0; scanf("%u%u%u",&n,&m,&k); init(n,m); for(int i=0;i<k;i++) { unsigned int r,c,z; scanf("%u%u%u",&r,&c,&z); if (!warownia((r^x)%n,(c^x)%m))x^=z; // rysuj(); } return 0; } |