#include #include using namespace std; const int MAXD = 1000; const int MAXW = 50000; const int HORZ = 0; const int VERT = 1; const int DIAG = 2; char grid[MAXD][MAXD]; class list { public: list(int i, list* n) { w = i; next = n; }; int w; list *next; }; struct wordt { string word; int r1, c1, r2, c2; int type; list *adj; bool visited; int dnum; int best; } wordList[MAXW]; int check(int i, int& dnum, int prev) { if(wordList[i].visited) return wordList[i].dnum; wordList[i].visited = true; wordList[i].dnum = dnum++; for(list* p=wordList[i].adj; p!=0; p=p->next) { if (p->w == prev) continue; int ans = check(p->w, dnum, i); if (ans == -1) return -1; if (ans < wordList[i].best) wordList[i].best = ans; } if (wordList[i].best >= wordList[i].dnum) return -1; return wordList[i].best; } bool check(int nwords) { if (nwords == 1) return true; if (wordList[0].adj == 0) return false; wordList[0].visited = true; wordList[0].dnum = 0; for(int i=1; iw, dnum, 0); if (ans == -1) return false; for(int i=0; i> s; for(i=0; i 'Z') s[i] += ('A'-'a'); wordList[iword].word = s; wordList[iword].adj = 0; len = s.length(); for(i=0; i= r1 && c3 >= c1 && c3 <= c2); } bool horzDiagInt(int r1, int c1, int c2, int r3, int r4, int c3, int c4) { if (r3 > r1 || r4 < r1) return false; int cint = c3+(r1-r3)*(c3-c4)/(r3-r4); return (cint >= c1 && cint <= c2); } bool vertDiagInt(int r1, int r2, int c1, int r3, int r4, int c3, int c4) { if (c3 > c4) { int temp = c3; c3 = c4; c4 = temp; temp = r3; r3 = r4; r4 = temp; } if (c3 > c1 || c4 < c1) return false; int rint = r3+(c1-c3)*(r3-r4)/(c3-c4); return (rint >= r1 && rint <= r2); } bool diagDiagInt(int r1, int r2, int c1, int c2, int r3, int r4, int c3, int c4) { if ((r1+c1)%2 != (r3+c3)%2) return false; bool downright1 = (c2>c1); bool downright3 = (c4>c3); if (downright1 && downright3) { if (r1-c1 != r3-c3) return false; return ((r1>=r3 && r1 <= r4) || (r3 >= r1 && r3<=r2)); } else if (!downright1 && !downright3) { if (r1+c1 != r3+c3) return false; return ((r1>=r3 && r1 <= r4) || (r3 >= r1 && r3<=r2)); } else if (downright1 && !downright3) { int u = (r3+c3-(r1+c1))/2; if (u < 0 || u > (r2-r1)) return false; int t = (r1-c1-(r3-c3))/2; return (t>=0 && t<=(r4-r3)); } else { int u = (r3-c3-(r1-c1))/2; if (u < 0 || u > (r2-r1)) return false; int t = (r1+c1-(r3+c3))/2; return (t>=0 && t<=(r4-r3)); } } void addToLists(int iword, int i) { wordList[iword].adj = new list(i, wordList[iword].adj); wordList[i].adj = new list(iword, wordList[i].adj); } void checkIntersect(int iword) { int r1 = wordList[iword].r1; int c1 = wordList[iword].c1; int r2 = wordList[iword].r2; int c2 = wordList[iword].c2; int type = wordList[iword].type; for(int i=0; i= c1 && c3 <= c2) || (c1 >= c3 && c1 <= c4))) { addToLists(iword, i); } break; case VERT : if (horzVertInt(r1, c1, c2, r3, r4, c3)) { addToLists(iword, i); } break; case DIAG : if (horzDiagInt(r1, c1, c2, r3, r4, c3, c4)) { addToLists(iword, i); } break; } break; case VERT : switch (type2) { case HORZ : if (horzVertInt(r3, c3, c4, r1, r2, c1)) { addToLists(iword, i); } break; case VERT : if ((c1==c3) && ((r3 >= r1 && r3 <= r2) || (r1 >= r3 && r1 <= r4))) { addToLists(iword, i); } break; case DIAG : if (vertDiagInt(r1, r2, c1, r3, r4, c3, c4)) { addToLists(iword, i); } break; } break; case DIAG : switch (type2) { case HORZ : if (horzDiagInt(r3, c3, c4, r1, r2, c1, c2)) { addToLists(iword, i); } break; case VERT : if (vertDiagInt(r3, r4, c3, r1, r2, c1, c2)) { addToLists(iword, i); } break; case DIAG : if (diagDiagInt(r1, r2, c1, c2, r3, r4, c3, c4) ){ addToLists(iword, i); } break; } } } } int main() { int n, m, nwords, i, j; cin >> n >> m >> nwords; while (n > 0) { for(i=0; i> grid[i][j]; for(i=0; i> n >> m >> nwords; } return 0; }